Количество нулевых битов в целом числе, кроме начальных нулей

Question

Если у меня есть целое число в Java, как мне посчитать, сколько битов равны нулю, кроме ведущих нулей?

Мы знаем, что целые числа в Java имеют 32 бита, но подсчет количества установленных битов в числе и вычитание из 32 не дает мне того, что я хочу, потому что это также включает ведущие нули.

Например, число 5 имеет один нулевой бит, потому что в двоичном виде это 101.

Answer 1

Посмотрите на документацию API Integer :

32 - Integer.numberOfLeadingZeros(n) - Integer.bitCount(n)

Answer 2

Чтобы подсчитать не ведущие нули в Java, вы можете использовать этот алгоритм:

public static int countNonleadingZeroBits(int i)
{
    int result = 0;
    while (i != 0)
    {
        if (i & 1 == 0)
        {
            result += 1;
        }
        i >>>= 1;
    } 
    return result;
}

Этот алгоритм будет достаточно быстрым, если ваши входные данные обычно малы, но если ваши входные данные обычно больше, он можетБыстрее использовать вариант одного из алгоритмов битового взлома на этой странице .

Answer 3

Вот что я бы сделал.

public static int countBitsSet(int num) {
    int count = num & 1; // start with the first bit.
    while((num >>>= 1) != 0) // shift the bits and check there are some left.
        count += num & 1; // count the next bit if its there.
    return count;
}

public static int countBitsNotSet(int num) {
    return 32 - countBitsSet(num);
}

Answer 4

Подсчитайте общее количество «бит» в вашем числе, а затем вычтите количество единиц из общего количества бит.

Answer 5

Использование некоторых встроенных функций:

public static int zeroBits(int i)
{
    if (i == 0) {
        return 0;
    }
    else {
        int highestBit = (int) (Math.log10(Integer.highestOneBit(i)) / 
                Math.log10(2)) + 1;
        return highestBit - Integer.bitCount(i);
    }
}

Answer 6

Так как порядок оценки в Java определен , мы можем сделать это:

public static int countZero(int n) {
    for (int i=1,t=0 ;; i<<=1) {
        if (n==0) return t;
        if (n==(n&=~i)) t++;
    }
}

Обратите внимание, что полагается на LHS равенства, которое оценивается первым;попробуйте то же самое в C или C ++, и компилятор может заставить вас выглядеть глупо, поджигая ваш принтер.