Check if bit is set on BigNum

Question

I have a bignum formatted like a string like this: "123456789123456789123456789" and I need to check if a specified bit is set. The components are single digits in this string.

Usually I would do it like this if I wanted to check if bit 54 is set: NyNumber&(1<<54)

The problem is that I don't have AND or SHIFT in the bignum library I'm using.

So the question is; How can I check if a bit is set in a number formatted like a string with arbitrary size?

Edit: Just to clarify: I'm using a small scripting language called Autoit3 with the following library: http://www.autoitscript.com/forum/topic/83529-bignum-udf which represents BigNums as strings.

Answer 1

First of all, you can (and should) use a library for handling Arbitrary Precision numbers.

In java you have BigInteger, and in C++ you can use Gnu's Big Num

If you don't want to do this (and I assume you are not looking for performance), you can:

• convert the string to it's 2-complement representation and check the index.

• create a bitwise and operation and convert the string with the binary representation of what index you want (for example "0100") to base 10.

• Bit shifting is the same as dividing by two, so, if you want to bitshift 54 bits, you should divide the number by 2^54. Then, you can just check if the number is even or odd, if it's even, then the bit isn't set.

If you are using the last method, you can do something like:

bool bitCheck (number, bitIndex) 
    pow = 2^bitIndex
    shifted = number / pow
    return (shifted % 2) == 0

ps: If you use gmp, you can check this page

Answer 2

Convert your string into binary string and then check the 54th index. For java, you may try BigInteger class instead.

    BigInteger bi = new BigInteger("123456789123456789123456789");
    boolean hasBitSet = bi.equals(bi.setBit(54)); 

Edit:

    byte[] b = "123456789123456789123456789".getBytes("US-ASCII");
    int maxIndex = b.length - 1;
    for (int bitIdx = 0; bitIdx < (b.length * 8); bitIdx++) {

        int index =  maxIndex - (bitIdx / 8);
        int remainder = bitIdx % 8;

        boolean hasBitSet = (((b[index] & 0xff)) & (1 << remainder)) != 0;
        System.out.println( bitIdx + (hasBitSet ? " has set" : " has not set") );

    }