-
Notifications
You must be signed in to change notification settings - Fork 187
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Bitwise zero-fill shift right #137
Comments
What should it return for negative numbers? |
Yaffle, see this: Example: console.log(
(-2>>1), //-1
//11111111111111111111111111111110 -> 11111111111111111111111111111111 = -1
(-2>>>1), //2147483647
//11111111111111111111111111111110 -> 01111111111111111111111111111111 = 2147483647
(-2<<3) //-16
//11111111111111111111111111111110 -> 11111111111111111111111111110000 -> -16
//(-2<<<8) //Uncaught SyntaxError: Unexpected token <
); I did convertation for negative numbers in modified NOT-function here: BigInteger.prototype.not = function (bits) {//bits default - undefined
var bits = (typeof bits === 'undefined') ? false : bits; //if undefined - false, else use this bits
var negated = this.negate().prev();
if(bits===false){//if false - return negated
return negated; //return (0-N)-1
}else{
//if bits was been specified
if(this.isNegative()){
return negated = this.abs().subtract(bigInt(1)); //-1 -(-n) = |n| - 1
}
else{
//2^bits-1 (bits number of one bits)
var ones = bigInt(1).shiftLeft(bits).subtract(bigInt(1));
return negated = ones.subtract(this.divmod(bigInt(1).shiftLeft(bits))['remainder']);
}
}
};
SmallInteger.prototype.not = BigInteger.prototype.not; and there user can specify bits, and return different positive numbers, like:
That means you can using this method to construct ">>>" bitwise operator using this method... P.S: But wait... See this code... BigInteger.js: BigInteger.prototype.shiftRight_positive = function (n, bits) { //analog <<<
var bits = (typeof bits === 'undefined') ? 32 : bits; //if undefined - false, else use this bits
if(this.isNegative() && (bits!==false)){
var ones = bigInt(1).shiftLeft(bits).subtract(bigInt(1));
return ones.add(this).shiftRight(n);
}else return this.shiftRight(n);
}
SmallInteger.prototype.shiftRight_positive = BigInteger.prototype.shiftRight_positive; test <script language="JavaScript" type="text/javascript" src="BigInteger.js"></script>
<script>
//from min to max
function getrandint(min, max) {
return Math.random() * (max+1 - min) + min;
}
var integer = getrandint(1, Math.pow(2,32));
var integer = 0-integer;
console.log(
'\n integer = ', integer,
'\n (integer>>>1) ', (integer>>>1), '"bigInt(integer).shiftRight_positive(1).toString()" = ', bigInt(integer).shiftRight_positive(1).toString(),
'\n (integer>>>8) ', (integer>>>8), '"bigInt(integer).shiftRight_positive(8)" = ', bigInt(integer).shiftRight_positive(8).toString(),
'\n (integer>>>10) ', (integer>>>10), '"bigInt(integer).shiftRight_positive(10)" = ', bigInt(integer).shiftRight_positive(10).toString(),
'\n Comparison with standart if bits = false: (bigInt(integer).shiftRight(10)).eq(bigInt(integer).shiftRight_positive(10, false)) === ', (bigInt(integer).shiftRight(10)).eq(bigInt(integer).shiftRight_positive(10, false))
);
</script> result:
Success. |
This if equivalent of <<< bitwise operation in JavaScript. n - how many bits to shifting, bitlength - can be specified, or be false to do standartly shiftRight(n). Default bitlength is 32 bits. See peterolson#137
@username1565 Your implementation of bigInt(1).shiftLeft(bits).subtract(bigInt(1)); |
@JasonHK ,
Where? Here: https://github.com/username1565/BigInteger.js/blob/2b2057db04a32996247f2d1182511b6f2fe82395/BigInteger.js#L1026 As I understand, there is used the number |
@username1565 Actually no. Let's use |
As you can see, that function, have name I do not remember, why I wrote that my post, in 2018, and why I implemented that function, But, I remember, in my bad memory...
If you want to use negative number of bits, //<!--bigInt, working, on html-page, after include this--><script src="BigInteger.js"></script>
//<script>
console.log( ( 15 >> 8 ) ); // -> 0
console.log( ( bigInt(15).shiftRight(8).toJSNumber() ) ); // -> 0
//OK
console.log( ( 15 >> -8 ) ); // -> 0
console.log( ( bigInt(15).shiftRight(-8).toJSNumber() ) ); // -> 3840 (!) - not the same, in shiftRight-function
//why?
console.log( ( bigInt(15).toString(2) ) ); // -> "1111"
console.log( ( bigInt(15).shiftRight(-8).toString(2) ) ); // -> "111100000000" - it's shifting left, maybe because -8 is not a positive nubmer.
console.log( ( -2147483648 >> 8 ) ); // -> -8388608
console.log( ( bigInt(-2147483648).shiftRight(8).toJSNumber() ) ); // -> -8388608
//OK
console.log( ( -2147483648 >> -8 ) ); // -> -128
console.log( ( bigInt(-2147483648).shiftRight(-8).toJSNumber() ) ); // -> -549755813888 (!) - not the same, in shiftRight-function
//why?
console.log( ( bigInt(-2147483648).toString(2) ) ); // -> "-10000000000000000000000000000000"
console.log( ( -2147483648 >> -8 ).toString(2) ); // -> "-10000000" (-128) - correct result.
console.log( ( bigInt(-2147483648).shiftRight(-8).toString(2) ) ); // -> "-1000000000000000000000000000000000000000" - it's shifting left, maybe because -8 is not a positive nubmer.
//shift_right_to_positive:
console.log( ( 15 >>> 8 ) ); // -> 0
console.log( ( bigInt(15).shiftRight(8, 4).toJSNumber() ) ); // -> 0
//OK
console.log( ( 15 >>> -8 ) ); // -> 0
console.log( ( bigInt(15).shiftRight_to_positive(-8).toJSNumber() ) ); // -> 3840 (!) - not the same, in shiftRight_to_positive-function
//Why?
console.log( ( bigInt(15).shiftRight_to_positive(-8).toString(2) ) ); // -> "111100000000" - it's shifting left, maybe because -8 is not a positive nubmer.
console.log( ( -2147483648 >>> 8 ) ); // -> 8388608
console.log( ( bigInt(-2147483648).shiftRight_to_positive(8).toJSNumber() ) ); // -> 8388608
//OK
console.log( ( -2147483648 >>> -8 ) ); // -> 128
console.log( ( bigInt(-2147483648).shiftRight_to_positive(-8).toJSNumber() ) ); // -> 549755813632 (!) - not the same result, in shiftRight_to_positive-function
//Why?
console.log( ( bigInt(-2147483648).toString(2) ) ); // -> "-10000000000000000000000000000000"
console.log( ( bigInt(-2147483648).shiftRight_to_positive(-8).toString(2) ) ); // -> "111111111111111111111111111111100000000", some bull-shit.
//</script> Maybe this can help to fix this, because I don't know, what to do with this all, and how exactly it shoult work fine, with all possible numbers. Regards. |
@username1565 Hmmm, sorry for my bad explanation. It seems that my explanation wasn't clear enough. The basic of unsigned right shift is just to shift all bits to the right, including the sign bit, then return an unsigned value. The how should we implement it? We should first convert it to an unsigned value with the same bits, that shift it using signed right shift ( On the surface, -1 >>> 0; // -> 0b11111111111111111111111111111111
bigInt(-1).shiftRight_to_positive(0); // -> 0b11111111111111111111111111111110
-1585618145 >>> 0; // -> 0b10100001011111010110001100011111
bigInt(-1585618145).shiftRight_to_positive(0); // -> 0b10100001011111010110001100011110 As you can see, every value returned by The correct conversion should be something like this:
But the
That's why I said remove the And for the negative amount of bits (a.k.a. the number right |
@JasonHK <script src="BigInteger.js"></script>
<script>
//https://github.com/username1565/BigInteger.js/blob/2b2057db04a32996247f2d1182511b6f2fe82395/BigInteger.js#L1023-L1030
//this - replaced to big, and used as first argument, instead of this.
var shiftRight_to_positive2 = function (big, n, bitlength) { //equivalent >>>
var bitlength = (typeof bitlength === 'undefined') ? 32 : bitlength; //if undefined - false, else use this bitlength
var res;
if(big.isNegative() && (bitlength!==false)){ //negative -> to unsigned:
var ones = bigInt(1).shiftLeft(bitlength).subtract(bigInt(1)); //bitlength number of one bits.
var unsigned = ones.xor(big.abs().prev()); //ones XOR (|big|-1)
res = unsigned.shiftRight((n<0) ? bitlength-(0-n) : n);
}else{
res = big.shiftRight((n<0) ? 0-n : n);
}
return res;
}
// TESTS - compare, then show both. See console.log()
console.log(
'' , ( ( -5 >>> 2 ) === ( shiftRight_to_positive2(bigInt(-5), 2).toJSNumber() ) )
, '\n' , ( -5 >>> 2 )
, '\n' , ( shiftRight_to_positive2(bigInt(-5), 2).toJSNumber() )
, '\n'
, '\n' , ( ( -2147483648 >>> -8 ) === ( shiftRight_to_positive2(bigInt(-2147483648), -8).toJSNumber() ))
, '\n' , ( -2147483648 >>> -8 )
, '\n' , ( shiftRight_to_positive2(bigInt(-2147483648), -8).toJSNumber() )
, '\n'
, '\n' , ( ( 15 >>> 8 ) === ( shiftRight_to_positive2(bigInt(15), 8, 4).toJSNumber() ) )
, '\n' , ( 15 >>> 8 )
, '\n' , ( shiftRight_to_positive2(bigInt(15), 8, 4).toJSNumber() )
, '\n'
, '\n' , ( ( 15 >>> -8 ) === ( shiftRight_to_positive2(bigInt(15), -8).toJSNumber() ))
, '\n' , ( 15 >>> -8 )
, '\n' , ( shiftRight_to_positive2(bigInt(15), -8).toJSNumber() )
, '\n'
, '\n' , ( ( -2147483648 >>> 8 ) === ( shiftRight_to_positive2(bigInt(-2147483648), 8).toJSNumber() ))
, '\n' , ( -2147483648 >>> 8 )
, '\n' , ( shiftRight_to_positive2(bigInt(-2147483648), 8).toJSNumber() )
, '\n'
, '\n' , ( (-1 >>> 0) === ( shiftRight_to_positive2(bigInt(-1),0).toJSNumber(2) ) )
, '\n' , (-1 >>> 0)
, '\n' , ( shiftRight_to_positive2(bigInt(-1),0).toJSNumber(2) )
, '\n'
, '\n' , ( (-1585618145 >>> 0) === ( shiftRight_to_positive2(bigInt(-1585618145),0).toJSNumber(2) ))
, '\n' , (-1585618145 >>> 0)
, '\n' , ( shiftRight_to_positive2(bigInt(-1585618145),0).toJSNumber(2) )
);
</script> Need to test this with different numbers, and with different bitlengths. P.S.: Maybe this can be more optimized, minimized, and working faster, |
Add RSABigInteger, to make, using BigInteger, the following RSA operations: encryption/decryption, and sign/verify and make this for the bytearrays with arbitrary bytelength. Two functions allow to do it, now: RSABigInteger.EncryptBytes(key, src, byPriv) RSABigInteger.DecryptBytes(key, src, byPub) See changes in differences, and description of this - in comment for this commit.
Need to fix something, in previous code: var stop = 0;
for(var i = -2147483649; i<=2147483648; i++){
for(var j = -8; j<=8; j++){
var srp = ( i >>> j )
var srpb = ( bigInt(i).shiftRight_to_positive(j).toJSNumber() );
if(srp !== srpb){
console.log('i', i, 'j', j, 'srp', srp, 'srpb', srpb); //many-many fails
stop++
}
}
if(stop>100){break;}
} |
I think the
shiftLeft
andshiftRight
functions are equivalent to<<
and>>
for integers in JavaScript.Is it possible to do something equivalent to
>>>
?If not, could that be added?
The text was updated successfully, but these errors were encountered: