Количество Нулей в двоичном представлении Целого числа [дубликат]

В Интернете есть отличный ресурс под названием Bit Twiddling Hacks , который содержит всевозможные замечательные маленькие трюки C. Вас может особенно заинтересовать раздел Набор битов счета .

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

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

/* How many bits are set in every possible nibble. */
static size_t BIT_TABLE[] = {
    0, 1, 1, 2,     /* 0, 1, 2, 3 */
    1, 2, 2, 3,     /* 4, 5, 6, 7 */
    1, 2, 2, 3,     /* 8, 9, A, B */
    2, 3, 3, 4      /* C, D, E, F */
};

size_t num_of_bits(int num) {
    /* Little reworking could probably shrink the stack space in use here. */
    size_t ret = 0, i;
    register int work = num;

    /* Iterate every nibble, rotating the integer in place. */
    for(i = 0; i < (sizeof(num) * 2); i++) {
        /* Pointer math to get a member of the static array. */
        ret += *(BIT_TABLE + (work & 0xF));
        work >>= 4;
    }
    return ret;
}

Рекурсия определенно излишняя - и, кроме того, в вашем коде много ошибок (он не будет считать ни один из ведущих нулей num !!! ). Простая итерация, такая как:

int num_of_zero(int num) {
  unsigned int unum = (unsigned int)num;
  int count;
  int i;

  for(i = 0; i < 32; ++i) {
    if(!(unum & 1)) ++count;
    unum >>= 1;
  }
  return count;
}

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

Если вам приходится выполнять это вычисление много раз, рассмотрите возможность предварительного вычисления массива скажем) 256 «отсчетов нулей» (каждое значение дает счет для своего индекса, от 0 до 255, включая 8-битное число). Затем вы можете выполнить цикл всего 4 раза (маскируя и сдвигая 8 бит за раз) и легко развернуть цикл - если ваш компилятор недостаточно умен, чтобы сделать это от вашего имени; -).

На самом деле это не ответ на ваш главный вопрос, но вам следует переписать рекурсивную функцию следующим образом:

int num_of_zero(int num)
{
    int left_part_zeros;

    if (num == 0)
        return 0;

    left_part_zeros = num_of_zero(num >> 1);
    if ((num & 1) == 0)
        return left_part_zeros + 1;
    else
        return left_part_zeros;
}

У вашей реализации много проблем, помимо того, что она полностью нечитаема.

Самый простой способ, который я нашел, - это основать его на чем-то, что считает единицы, а затем просто вычесть это из 32 (при условии, что вы уверены int размер составляет 32 бита).

int numberOfOnes (int num) {
    int count = 0;
    unsigned int u = (unsigned int)num;
    while (u != 0) {
        if ((u&1) == 1)
            count++;
        u >>= 1;
    }
    return count;
}
int numberOfZeros (int num) {
    return 32 - numberOfOnes (num);
}

Это фактически дает вам оба варианта (единицы и нули) - есть более быстрые способы сделать это, но я бы не стал их рассматривать, если и пока вы не узнаете, что есть проблемы с производительностью. Я обычно сначала пишу код для удобства чтения.

Вы также можете захотеть хотя бы проверить возможность того, что поиск в таблице может быть быстрее (основная директива оптимизации - мера, не угадайте!

Одна возможность можно было бы заменить функцию numberOfOnes чем-то, что управляет нубайтом за раз:

int numberOfOnes (int num) {
    static const count[] = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
    };
    int retval = 0;
    unsigned int u = (unsigned int)num;
    while (u != 0) {
        retval += count[u & 0x0f]
        u >>= 4;
    }
    return retval;
}

Я предполагаю, что это вопрос домашнего задания. Нет проблем! Вот самое быстрое из возможных решений (после больших затрат на запуск):

Создайте массив из байт длиной 2 ³² . Предварительно вычислите значение количества нулей в двоичном представлении для каждого возможного значения int для заполнения этого массива. С этого момента у вас будет массив, который будет давать вам количество нулей на значение.

Да, это решение глупо - это большая работа с небольшой прибылью - но объедините его с еще одной идеей:

Что произойдет, если вы просто предварительно вычислите значения длиной 8 бит? Сможете ли вы написать код, который хоть и не так быстро, все равно будет возвращать количество 0-бит в int?

Что произойдет, если вы просто предварительно вычислите значения длиной 4 бита? 2 бита? 1 бит?

Надеюсь, это даст вам идеи для лучшего алгоритма ...