Проверьте, установлен ли бит на BigNum

Question

У меня есть bignum, отформатированный как строка вроде этой: "123456789123456789123456789", и мне нужно проверить, установлен ли указанный бит.Компоненты представляют собой однозначные числа в этой строке.

Обычно я делал бы это так, если бы хотел проверить, установлен ли бит 54: NyNumber & (1 << 54) </p>

Проблема заключается вУ меня нет ни AND, ни SHIFT в используемой библиотеке bignum.

Итак, вопрос в том,Как я могу проверить, установлен ли бит в число, отформатированное как строка с произвольным размером?

Редактировать: Просто чтобы уточнить: я использую небольшой язык сценариев под названием Autoit3 сследующая библиотека: http://www.autoitscript.com/forum/topic/83529-bignum-udf, которая представляет BigNums в виде строк.

Answer 1

Прежде всего, вы можете (и должны) использовать библиотеку для обработки чисел произвольной точности.

В Java у вас есть BigInteger , а в C ++ вы можете использовать Big Num Gnu

Если вы не хотите этого делать (и я предполагаю, что вы не ищете производительность), вы можете:

• преобразовать строку в представление из 2-х дополнений и проверить индекс.

• создайте побитовые операции и и преобразуйте строку с двоичным представлением того, какой индекс вы хотите (например, "0100") в основание 10.

• Сдвиг битов аналогичен делению на два, поэтому, если вы хотите сдвинуть бит на 54 бита, вам следует разделить число на 2 ^ 54 . Затем вы можете просто проверить, является ли число четным или нечетным, если оно четное, тогда бит не установлен.

Если вы используете последний метод, вы можете сделать что-то вроде:

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

ps: если вы используете gmp, вы можете проверить эту страницу

Answer 2

Преобразуйте вашу строку в двоичную строку, а затем проверьте 54-й индекс. Для Java вы можете попробовать BigInteger class вместо.

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

Редактировать

    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") );

    }