How to do bitwise AND in javascript on variables that are longer than 32 bit?

Question

I have 2 numbers in javascript that I want to bit and. They both are 33bit long

in C#:

 ((4294967296 & 4294967296 )==0) is false

but in javascript:

 ((4294967296 & 4294967296 )==0) is true

4294967296 is ((long)1) << 32

As I understand it, it is due to the fact that javascript converts values to int32 when performing bit wise operations.

How do I work around this? Any suggestions on how to replace bit and with a set of other math operations so that bits are not lost?

Answer 1

Here's a fun function for arbitrarily large integers:

function BitwiseAndLarge(val1, val2) {
    var shift = 0, result = 0;
    var mask = ~((~0) << 30); // Gives us a bit mask like 01111..1 (30 ones)
    var divisor = 1 << 30; // To work with the bit mask, we need to clear bits at a time
    while( (val1 != 0) && (val2 != 0) ) {
        var rs = (mask & val1) & (mask & val2);
        val1 = Math.floor(val1 / divisor); // val1 >>> 30
        val2 = Math.floor(val2 / divisor); // val2 >>> 30
        for(var i = shift++; i--;) {
            rs *= divisor; // rs << 30
        }
        result += rs;
    }
    return result;
}

Assuming that the system handles at least 30-bit bitwise operations properly.

Answer 2

You could split each of the vars into 2 32-bit values (like a high word and low word), then do a bitwise operation on both pairs.

The script below runs as a Windows .js script. You can replace WScript.Echo() with alert() for Web.

var a = 4294967296;
var b = 4294967296;

var w = 4294967296; // 2^32

var aHI = a / w;
var aLO = a % w;
var bHI = b / w;
var bLO = b % w;

WScript.Echo((aHI & bHI) * w + (aLO & bLO));

Answer 3

There are several BigInteger librairy in Javascript, but none of them offer bitwise operation you need at the moment. If you are motivated and really need that functionality you can modify one of those librairy and add a method to do so. They already offer a good code base to work with huge number.

You can find a list of the BigInteger librairy in Javascript in this question :

Huge Integer JavaScript Library

Answer 4

The simplest bit-wise AND, that works up to JavaScript's maximum number

JavaScript's max integer value is 2^53 for internal reasons (it's a double float). If you need more there are good libraries for that big integer handling.

2^53 is 9,007,199,254,740,992, or about 9,000 trillion (~9 quadrillion).

// Works with values up to 2^53
function bitwiseAnd_53bit(value1, value2) {
    const maxInt32Bits = 4294967296; // 2^32

    const value1_highBits = value1 / maxInt32Bits;
    const value1_lowBits = value1 % maxInt32Bits;
    const value2_highBits = value2 / maxInt32Bits;
    const value2_lowBits = value2 % maxInt32Bits;
    return (value1_highBits & value2_highBits) * maxInt32Bits + (value1_lowBits & value2_lowBits)
}

Answer 5

Ran into this problem today and this is what I came up with:

function bitwiseAnd(firstNumber, secondNumber) {
    let // convert the numbers to binary strings
        firstBitArray = (firstNumber).toString(2),
        secondBitArray = (secondNumber).toString(2),
        resultedBitArray = [],
        // get the length of the largest number
        maxLength = Math.max(firstBitArray.length, secondBitArray.length);

        //add zero fill ahead in case the binary strings have different lengths
        //so we can have strings equal in length and compare bit by bit
        firstBitArray = firstBitArray.padStart(maxLength,'0');
        secondBitArray = secondBitArray.padStart(maxLength,'0');

        // bit by bit comparison
        for(let i = 0; i < maxLength; i++) {
            resultedBitArray.push(parseInt(firstBitArray[i]) && secondBitArray[i]);
        }

        //concat  the result array back to a string and parse the binary string back to an integer
        return parseInt(resultedBitArray.join(''),2);
}

Hope this helps anyone else who runs into this problem.