Bitwise zero-fill shift right #137

paulyoung · 2018-06-03T04:04:56Z

I think the shiftLeft and shiftRight 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:

Yaffle · 2018-06-03T04:44:05Z

What should it return for negative numbers?

username1565 · 2018-06-03T09:22:56Z

Yaffle, see this:
The triple >>> operator, after doing its unsigned operation, converts the results of its calculation to Number as an unsigned integer rather than the signed integer the others do, so it can be used to convert negatives to the 32-bit-two's-complement version as a large Number. Using >>>0 ensures you've got an integer between 0 and 0xFFFFFFFF.

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:
https://github.com/username1565/BigInteger.js
and this depeding from bitlength.

    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:

bigInt(1).not(8); 8 bits, ~1 = -2, ~00000001 = 11111110 = return 254 (= 2^8 - 2);
bigInt(1).not(16); 16 bits, ~1 = -2, ~0000000000000001 = 1111111111111110 = return 65534 (= 2^16 - 2 = 65536 - 2);

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:

integer =  -1585618145 
 (integer>>>1)  1354674575 "bigInt(integer).shiftRight_positive(1).toString()" =  1354674575 
 (integer>>>8)  10583395 "bigInt(integer).shiftRight_positive(8)" =  10583395 
 (integer>>>10)  2645848 "bigInt(integer).shiftRight_positive(10)" =  2645848 
 Comparison with standart if bits = false: (bigInt(integer).shiftRight(10)).eq(bigInt(integer).shiftRight_positive(10, false)) ===  true

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

JasonHK · 2020-12-09T17:31:50Z

Yaffle, see this:
The triple >>> operator, after doing its unsigned operation, converts the results of its calculation to Number as an unsigned integer rather than the signed integer the others do, so it can be used to convert negatives to the 32-bit-two's-complement version as a large Number. Using >>>0 ensures you've got an integer between 0 and 0xFFFFFFFF.

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:
https://github.com/username1565/BigInteger.js
and this depeding from bitlength.

    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:

bigInt(1).not(8); 8 bits, ~1 = -2, ~00000001 = 11111110 = return 254 (= 2^8 - 2);
bigInt(1).not(16); 16 bits, ~1 = -2, ~0000000000000001 = 1111111111111110 = return 65534 (= 2^16 - 2 = 65536 - 2);

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:

integer =  -1585618145 
 (integer>>>1)  1354674575 "bigInt(integer).shiftRight_positive(1).toString()" =  1354674575 
 (integer>>>8)  10583395 "bigInt(integer).shiftRight_positive(8)" =  10583395 
 (integer>>>10)  2645848 "bigInt(integer).shiftRight_positive(10)" =  2645848 
 Comparison with standart if bits = false: (bigInt(integer).shiftRight(10)).eq(bigInt(integer).shiftRight_positive(10, false)) ===  true

Success.

@username1565 Your implementation of >>> is incorrect, you should not subtract one here:

bigInt(1).shiftLeft(bits).subtract(bigInt(1));

username1565 · 2020-12-09T18:19:21Z

@JasonHK ,

@username1565 Your implementation of >>> is incorrect, you should not subtract one here:
bigInt(1).shiftLeft(bits).subtract(bigInt(1));

Where? Here: https://github.com/username1565/BigInteger.js/blob/2b2057db04a32996247f2d1182511b6f2fe82395/BigInteger.js#L1026
??

As I understand, there is used the number bits of ones,
and when 5 bits, so 5 ones generating there 11111.
To get this number, need to <<< the nubmer 1 to 5 bits: 1 -> 100000,
and then subtract 1, from this result: 100000 - 1 = 11111;

JasonHK · 2020-12-10T07:10:16Z

@JasonHK ,

Where? Here: https://github.com/username1565/BigInteger.js/blob/2b2057db04a32996247f2d1182511b6f2fe82395/BigInteger.js#L1026
??

As I understand, there is used the number bits of ones,
and when 5 bits, so 5 ones generating there 11111.
To get this number, need to <<< the nubmer 1 to 5 bits: 1 -> 100000,
and then subtract 1, from this result: 100000 - 1 = 11111;

@username1565 Actually no. Let's use -8(1000) in 4-bit as an example: when 15 + -8, the result is 7(0111), not 8(1000). You can try this number: -2147483648, your implementation produces an incorrect result.

username1565 · 2020-12-11T07:58:46Z

@JasonHK

@username1565 Actually no. Let's use -8(1000) in 4-bit as an example: when 15 + -8,
the result is 7(0111), not 8(1000).
You can try this number: -2147483648, your implementation produces an incorrect result.
According the function, from previous link, I want to ask you the following thing:
Bits of what number (BigInteger "this"), with how much bitlength of this number (integer "bitlength"),
do you want to shift right, on what number of bits (integer "n"),
and where do you see an incorrect result, and what result should to be?
Can you describe this as binary values with shifting bits of this?

As you can see, that function, have name shiftRight_to_positive,
while previous function (implement of >>)
have the old name shiftRight.

I do not remember, why I wrote that my post, in 2018, and why I implemented that function,
and as you can see, in the source code of my version of BigInteger.js,
this function not used, and not called anywhere.
Maybe, just because >>> was not been implemented,
or I wanted to generate random large BigIntegers, faster,
just by shifting right, the negative nubmers, with specified bitlength of bigIntegers, to discard (32 bits limit for integer in JS >>>).

But, I remember, in my bad memory...
Why shiftRight_to_positive was been writted?
Just because shift_right https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Right_shift
have some difference from this: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Unsigned_right_shift
and second parameter "bitlength", in that function, allow to specify the number of bits for bigInteger "this", before shifting of this.
Of course, maybe, the nubmer of bits to shifting, must to be a positive number.
But you say

-8(1000), in 4 bit
and this is equals of
8 (1000), in 4 bit, too.
So I do not understand what you want to shift, and how.

If you want to use negative number of bits,
I can propose to see the some tests of this:

//<!--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.

JasonHK · 2020-12-11T14:06:01Z

@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, bigInt(-1).shiftRight_to_positive(1) and -1 >>> 1, bigInt(-1585618145).shiftRight_to_positive(1) and -1585618145 >>> 1 returns the correct value. That means the implementation should be correct, right? No, try to shift the value using >>> 0.

-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 .shiftRight_to_positive() is the correct value subtracted by one. This issue was caused by the faulty signed-to-unsigned conversion.

The correct conversion should be something like this:

        -1: 0b11111111111111111111111111111111 (signed)
4294967295: 0b11111111111111111111111111111111 (unsigned)

But the .shiftRight_to_positive() is this:

        -1: 0b11111111111111111111111111111111 (signed)
4294967294: 0b11111111111111111111111111111110 (unsigned)

That's why I said remove the .subtract(bigInt(1)) will fix the issue.

And for the negative amount of bits (a.k.a. the number right *not here* >>> *here*), I would consider it as undefined behaviour. Although JavaScript (and Java as well) seems to cast it to unsigned value just like what I did above.

username1565 · 2020-12-11T17:30:21Z

@JasonHK
Ok, thanks for your explanations, and examples.
I did not read that all, in detail, but it seems, like this function is working with all this 7 tests:

<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.
To add this into bigInteger, in that place, just copy and paste code from function, and replace big to this.

P.S.: Maybe this can be more optimized, minimized, and working faster,
so I just leave this variant of working example, here, to let anyone optimize it.

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.

username1565 · 2020-12-23T08:30:16Z

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;}
}

This was referenced Jun 6, 2018

zshr purescript-contrib/purescript-bigints#21

Closed

Right shift paulyoung/purescript-murmur3#3

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Bitwise zero-fill shift right #137

Bitwise zero-fill shift right #137

paulyoung commented Jun 3, 2018

Yaffle commented Jun 3, 2018

username1565 commented Jun 3, 2018

JasonHK commented Dec 9, 2020

username1565 commented Dec 9, 2020 •

edited

Loading

JasonHK commented Dec 10, 2020

username1565 commented Dec 11, 2020 •

edited

Loading

JasonHK commented Dec 11, 2020

username1565 commented Dec 11, 2020 •

edited

Loading

username1565 commented Dec 23, 2020 •

edited

Loading

Bitwise zero-fill shift right #137

Bitwise zero-fill shift right #137

Comments

paulyoung commented Jun 3, 2018

Yaffle commented Jun 3, 2018

username1565 commented Jun 3, 2018

JasonHK commented Dec 9, 2020

username1565 commented Dec 9, 2020 • edited Loading

JasonHK commented Dec 10, 2020

username1565 commented Dec 11, 2020 • edited Loading

JasonHK commented Dec 11, 2020

username1565 commented Dec 11, 2020 • edited Loading

username1565 commented Dec 23, 2020 • edited Loading

username1565 commented Dec 9, 2020 •

edited

Loading

username1565 commented Dec 11, 2020 •

edited

Loading

username1565 commented Dec 11, 2020 •

edited

Loading

username1565 commented Dec 23, 2020 •

edited

Loading