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

Question

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

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

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

Answer 1

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

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

Этот алгоритм будет достаточно быстро, если ваши входы, как правило, небольшие, но если ваш вход, как правило, большее количество может быть быстрее использовать вариацию на одном из алгоритмов бит-хака на this page.

Answer 2

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

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

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

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++, и компилятор может заставить вас выглядеть глупо, если вы загорелись.

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

Взгляните на документацию API в Integer:

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