Enhancement: bit test?

[gardhr]

I know we can test a bit like this:

function bit_test(value, bit)
{
    return BigInt.one.shiftLeft(bit).and(value).notEquals(BigInt.zero);
}

Is there a more efficient way this could be done internally that might justify adding it to the API?

[username1565]

@gardhr

` ` ` t e x t
Is there a more efficient way this could be done
` ` `

Each bit in shifted n_bits "value" in your function do logic AND with null recursivelly. So you can just do

shifted(value).mod(bigInt('2')).eq(bigInt('1')) //true for odd (last bit 1), and false for even (last bit 0)
//mod no need to do AND for each bit.

But mod function have so large code!.. And not effective to test many bits. So, I recommend you just to see the functions: .isEven()

    SmallInteger.prototype.isOdd = function () {
        return (this.value & 1) === 1;
    };

and the function .isOdd() :

   BigInteger.prototype.isOdd = function () {
        return (this.value[0] & 1) === 1;
    };

As you can see, in last function using this.value[0]; and this is faster to do AND.

For example:

var x = bigInt('41030010405074433410304979182411');
console.log(x.value[0]) //9182411 - only last 7 digits
//and...
///(x%2 === 9182411%2) && (x AND 1 === 9182411 AND 1) 

After this all:

function bit_test(value, bit)
{
        //check value and bit
    if(!bigInt.isInstance(value)){throw new Error("Function bit_test: value not a bigInteger");}
    if(typeof bit==='undefined'){var bit = 1;}
    if(!Number.isInteger(bit) && bigInt.isInstance(bit)){bit = bit.toJSNumber();}
    else if(!Number.isInteger(bit) && !bigInt.isInstance(bit)){throw new Error("Function bit_test: bit not a nubmer");} 

    return ((value.shiftRight(bit-1).value[0] || value.shiftRight(bit-1).value) & 1) //=== 1; //uncomment this if you need true or false
}

//test
var test = bigInt.randBetween('1', '1e8'); //rand int
var bit_number = bigInt.randBetween(bigInt('1'), test.bitLength()); //rand bit

var test_bin = test.toString(2); //binary string
//show this bit
var bits_before_bit = test_bin.substring(0, test_bin.length-bit_number.toJSNumber());
var bit_in_string = test_bin.substring(test_bin.length-bit_number.toJSNumber(), test_bin.length-bit_number.toJSNumber()+1);
var bits_after_bit = test_bin.substring(test_bin.length-bit_number.toJSNumber()+1, test_bin.length);
//new string with big bit
var test_bin = bits_before_bit+'<big><b>'+bit_in_string+'</b></big>'+bits_after_bit;
var bit_test = bit_test(test, bit_number);

document.write(
    '<br><br>'
    ,'Generated test number: ', test.toString() //number
    ,'<br>test -> to bin: ', test_bin, ' (',test.bitLength().toString(), 'bits)' //bin string with bitlength
    ,'<br>'+bit_number.toString()+'-th bit value: ', bit_test//n-th bit
    ,'<br>(bit_test === parseInt(bit_in_string)): ', (bit_test === parseInt(bit_in_string))
);

In this function checking only last digits (value[0]) of shifted bigInteger, or .value (if value not an array and shifted biginteger is small). but this function do more checking before!.. If your parameters (value and bit) are good pre-formatted, you can do not using check functions, comment this and make check bit working more faster.

[peterolson]

I think it would be more efficient to use the isOdd or isEven functions, as pointed out above. I don't think this is a common enough need to warrant adding it into the library.

[gardhr]

@peterolson

Looks like my confusion ultimately stemmed from the fact that I really don't understand the magic behind your methods! This for example gave some pretty puzzling results (for the big integer test at least).

BigInt.prototype.testBit = function (index) {
    function test(value, index) {
        return ((value / (1 << index)) & 1) !== 0;
    }
    if(this.value.length === undefined)
        return test(this.value, index);
/*
    Maximum integer that can fit in a JS number is 2^53-1 so...
*/  
    var width = 53;
    var offset = Math.floor(index / width);
    return test(this.value[offset], index % width);
};

function verify(number) {
    var log = console.log;
    var result = "";
    var index = number.bitLength();
    while(index--)
        result += number.testBit(index) ? "1" : "0"; 
    var control = number.toString(2);
    log("number: ", number.toString());
    log("control: ", control);    
    log("result:  ", result);    
    log("*** ", control == result ? "PASS" : "FAIL", " ***");
}   

/*
    Small integer passes
*/
verify(BigInt("1234567"));
/*
    True big integer fails
*/
verify(BigInt("123456789012345678901234567890123456789012345678901234567890"));

So in a nutshell an array element indexing scheme just isn't going to work here, correct?

And on a side note, can you point to any literature that might help explain to a simpleton like myself just how exactly your implementation actually works? It's quite a mystery to me!

Anyway, just wanted to say thanks for putting together this awesome library. However it does work, the performance is quite impressive!

@username1565

Thanks for the suggestion. I'll use something along those lines then.

[peterolson]

BigInt values are stored in a small-endian base 10000000 array.

[username1565]

@gardhr to see bigInt structure, or array You can use

console.log(number);
console.log(number.value);
console.log(number.value[0]);

Also, working example - available here: https://username1565.github.io/BigInteger.js/testbit_example.html This working for bigIntegers. There generated 1e128 random integer (10^128)

To copy this, just download BigInteger.js or _.min.js, create near this file html.page, put this code https://github.com/username1565/BigInteger.js/blob/master/testbit_example.html to this page inside and open in browser.

You can scroll a long binary string to see bold value of test bit. Comparison included. Your example added there. See source code.

[gardhr]

@username1565

Works great. Many thanks!