Как найти ведущее число нулей в числе, используя C

Question

например, если у меня есть номер 64, то его двоичное представление будет 0000 0000 0000 0000 0000 0000 0100 0000, поэтому начальное число нулей равно 25. помните, я должен рассчитать это за O (1) раз.

скажите, пожалуйста, правильный способ сделать это. Даже если ваша сложность> O (1), пожалуйста, опубликуйте свой ответ. спасибо

Answer 1

Я только что нашел эту проблему в верхней части результатов поиска и этот код:

int pop(unsigned x) {
    unsigned n;
    n = (x >> 1) & 033333333333;
    x = x - n;
    n = (n >> 1) & 033333333333;
    x = x - n;
    x = (x + (x >> 3)) & 030707070707;
    return x % 63;
}

int nlz(unsigned x) {
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >>16);
    return pop(~x);
}

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

Я не заметил, вопрос был о 64-битных числах, поэтому здесь:

int nlz(unsigned long x) {
    unsigned long y;
    long n, c;
    n = 64;
    c = 32;
    do {
        y = x >> c;
        if (y != 0) {
            n = n - c;
            x = y;
        }
        c = c >> 1;
    } while (c != 0);
    return n - x;
}

- это 64-битный алгоритм, опять же в несколько раз быстрее, чем упомянутое выше.

Answer 2

См. здесь для получения информации о 32-разрядной версии и других замечательных хитростях.

// this is like doing a sign-extension
// if original value was   0x00.01yyy..y
// then afterwards will be 0x00.01111111
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
x |= (x >> 32);

и после этого вам просто нужно вернуть 64 - numOnes (x).Простой способ сделать это - numOnes32 (x) + numOnes32 (x >> 32), где numOnes32 определен как:

int numOnes32(unsigned int x) {
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return(x & 0x0000003f);
}

Я не пробовал этот код, но это должно сделать numOnes64 напрямуюза меньшее время):

int numOnes64(unsigned long int x) {
     x = ((x >> 1) & 0x5555555555555555L) + (x & 0x5555555555555555L);
     x = ((x >> 2) & 0x3333333333333333L) + (x & 0x3333333333333333L);
     // collapse:
     unsigned int v = (unsigned int) ((x >>> 32) + x);
     v = ((v >> 4) + v) & 0x0f0f0f0f) + (v & 0x0f0f0f0f);
     v = ((v >> 8) & 0x00ff00ff) + (v & 0x00ff00ff);
     return ((v >> 16) & 0x0000ffff) + (v & 0x0000ffff);
}

Answer 3

Сдвиг вправо твой друг.

    int input = 64;
    int sample = ( input < 0 ) ? 0 : input;
    int leadingZeros = ( input < 0 ) ? 0 : 32;

    while(sample) {
        sample >>= 1;
        --leadingZeros;
    }
    printf("Input = %d, leading zeroes = %d\n",input, leadingZeros);

Answer 4

Я бы пошел с:

unsigned long clz(unsigned long n) {
    unsigned long result = 0;
    unsigned long mask = 0;
    mask = ~mask;
    auto size = sizeof(n) * 8;
    auto shift = size / 2;
    mask >>= shift;
    while (shift >= 1) {
        if (n <= mask) {
            result += shift;
            n <<= shift;
        }
        shift /= 2;
        mask <<= shift;
    }
    return result;
}

Answer 5

Использование плавающих точек не является правильным ответом ....

Вот алгоритм, который я использую для подсчета ТРЕЙЛИНГА 0 ... измените его на Ведущий ... Этот алгоритм находится в O (1) (всегда выполняется в одно и то же время или даже в одно и то же время на некотором процессоре).

int clz(unsigned int i)
{
  int zeros;
  if ((i&0xffff)==0) zeros= 16, i>>= 16; else zeroes= 0;
  if ((i&0xff)==0) zeros+= 8, i>>= 8;
  if ((i&0xf)==0) zeros+= 4, i>>= 4;
  if ((i&0x3)==0) zeros+= 2, i>>= 2;
  if ((i&0x1)==0) zeros+= 1, i>>= 1;
  return zeroes+i;
}

Answer 6

Поскольку основание логарифма 2 приблизительно представляет число битов, необходимое для представления числа, это может быть полезно в ответе:

irb(main):012:0> 31 - (Math::log(64) / Math::log(2)).floor()
=> 25
irb(main):013:0> 31 - (Math::log(65) / Math::log(2)).floor()
=> 25
irb(main):014:0> 31 - (Math::log(127) / Math::log(2)).floor()
=> 25
irb(main):015:0> 31 - (Math::log(128) / Math::log(2)).floor()
=> 24

Конечно, одним из недостатков использования log(3) является то,является подпрограммой с плавающей точкой;вероятно, есть несколько очень хитрых хитростей, чтобы найти число ведущих нулевых битов в целых числах, но я не могу вспомнить ни одного из них ...