Быстрая и грубая оценка количества значащих двоичных цифр в заданном неотрицательном числе

#алгоритм #численные_методы

Собственно, знаю о решении в лоб - двоичном логарифме, и итерационной его реализации
для целого результата: D сдвигов вправо, пока заданное число N > 0:
int D = 0;
while (N > 0) {
    N = N >> 1;
    D++;
}

Но существует ли какой-либо хак, чтобы получить результат быстрее, чем сдвигами в
цикле? (возможно, пожертвовав точностью)    

Ответы

Ответ 1

Количество нулевых бит в 64-разрядном целом
// adapted from Hacker's Delight
int clzll(uint64_t x) {
  int n;

  if (x == 0) return(64);
  n = 0;
  if (x <= 0x00000000FFFFFFFFL) {n = n + 32; x = x << 32;}
  if (x <= 0x0000FFFFFFFFFFFFL) {n = n + 16; x = x << 16;}
  if (x <= 0x00FFFFFFFFFFFFFFL) {n = n + 8; x = x << 8;}
  if (x <= 0x0FFFFFFFFFFFFFFFL) {n = n + 4; x = x << 4;}
  if (x <= 0x3FFFFFFFFFFFFFFFL) {n = n + 2; x = x << 2;}
  if (x <= 0x7FFFFFFFFFFFFFFFL) {n = n + 1;}
  return n;
}

Дальше подсчитать несложно.


Ответ 2

Зачем терять точность? Ниже точная оценка числа единичных битов.
scanf("%u", &x);

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);

printf("%d\n", x);

или
scanf("%u", &x);

x = x - ((x >> 1) & 0x55555555); 
x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
x = (x + (x >> 4)) & 0x0F0F0F0F; 
x = x + (x >> 8); 
x = x + (x >> 16); 
x &= 0x0000003F;

printf("%d\n", x);

А, я, кажется, неверно понял вопрос, имелось в виду сколько разрядов, считая от левой
единицы? Вот код, дающий количество ведущих нулей, 32 - n даст количество значащих
разрядов.
unsigned int x;
unsigned int n = 1;

scanf("%u", &x);

if (x == 0) return(32);

if ((x >> 16) == 0) {n = n + 16; x = x <<16;}
if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
n = n - (x >> 31);

printf("%d\n", n);


Ответ 3

Можно сделать таблицу степеней 2 и проводить по ней бинарный поиск:
#include 

unsigned int table[32] = {
    0x00000001, 0x00000002, 0x00000004, 0x00000008,
    0x00000010, 0x00000020, 0x00000040, 0x00000080,
    0x00000100, 0x00000200, 0x00000400, 0x00000800,
    0x00001000, 0x00002000, 0x00004000, 0x00008000,
    0x00010000, 0x00020000, 0x00040000, 0x00080000,
    0x00100000, 0x00200000, 0x00400000, 0x00800000,
    0x01000000, 0x02000000, 0x04000000, 0x08000000,
    0x10000000, 0x20000000, 0x40000000, 0x80000000
};

int bits(unsigned int n) {
    int i=0, j=32, k=16;
    while(i>1;
    }
    return j;
}

int main() {
    int i;
    for(i=0;i<=0x100;i++)
        printf("0x%08X %d\n",i,bits(i));
    return 0;
}

P.S. А можно сделать бинарным поиском, но без таблицы :
int bits(unsigned int n) {
    int i=0, j=32, k=16;
    while(i>1;
    }
    return j;
}


Ответ 4

У многих процессоров есть подобная инструкция. Но писать под каждый процессор свою
реализацию не очень удобно.
В gcc есть встроенные функции __builtin_clz..., которые в случае поддержки процессора,
компилируются в соответствующие инструкции, иначе gcc сам генерит какой-то код.
В MSVS тоже есть нечто подобное, __lzcnt..., но в документации сказано, что разработчик
должен проверить поддержку этой операции процессором, иначе результат вызова непредсказуем.


Ответ 5

Исчо один вариант. С длинным сдвигом. Результат от 0 (для аргумента 0) до 32.
static int m[] = {0xffff0000, 0xff00, 0xf0, 0xC, 2};
int bits(unsigned long a) {
    int n=0;
    int k=16;
    int *m1 = m;
    while(k) {
        if(a&*m1++) {
            n += k;
            a >>= k;
        }
        k >>= 1;
    }
    return a?n+1:n; // (0..31) => (1..32) для a != 0
}

Любители сишных трюков могут перенести сдвиг k в заголовок while для большей кучерявости
(тогда нач. значение k будет 32)


Ответ 6

Странно, что никто не предложил использовать массив в качестве хэша:
int f(unsigned int n)
{
  static const int bitsByNum[16] = {1,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4};

  int removed = 0;
  if (n > (unsigned int)0xFFFF)
  {
    removed += 16;
    n >>= 16;
  }
  if (n > (unsigned int)0xFF)
  {
    removed += 8;
    n >>= 8;
  }
  if (n > (unsigned int)0xF)
  {
    removed += 4;
    n >>= 4;
  }
  return removed + bitsByNum[n];
}


Ответ 7

Можно еще так попробовать, правда сомневаюсь, что это даст выиграш производительности,
разве что на числах очень большой разрядности: 
Предположим у вас есть N-битное число Y.
делаем xor между старшими N/2 битами числа и N/2 младшими (повторяем необходимое
количество раз)
результат каждой итерации имеет точность 0.5-1.0 от реального значения (т.е точность
2х будет 0.25 - 1, 0,0625 - 1).
Можно подобрать необходимое количество итераций, а что более важно можно будет прогнать
на реальных данных даную функцию и сравнивать ее точность с точностью исходного алгоритма
(приведенного в теле вопроса)


Ответ 8

А если так (на Java):
int d=Integer.toBinaryString(N).length();