Количество бит в 64-битном (длинном, большом) значении?

Ответ 1

Здесь вы можете найти 64-битную версию http://en.wikipedia.org/wiki/Hamming_weight

Это что-то вроде этого

static long NumberOfSetBits(long i)
{
    i = i - ((i >> 1) & 0x5555555555555555);
    i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
    return (((i + (i >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56;
}

Это 64-битная версия формы кода здесь Как подсчитать количество битов в 32-битовом целое?

Используя предложение Джошуа, я бы превратил его в это:

static int NumberOfSetBits(ulong i)
{
    i = i - ((i >> 1) & 0x5555555555555555UL);
    i = (i & 0x3333333333333333UL) + ((i >> 2) & 0x3333333333333333UL);
    return (int)(unchecked(((i + (i >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56);
}

EDIT. Я обнаружил ошибку при тестировании 32-разрядной версии. Я добавил отсутствующие круглые скобки. Сумма должна быть выполнена до побитового &, в последней строке

EDIT2 Добавлена ​​безопасная версия для ulong

Ответ 2

Быстрый (и более переносимый, чем использование нестандартных расширений компилятора):

int bitcout(long long n)
{
   int ret=0;
   while (n!=0)
   {
       n&=(n-1);
       ret++;
   }
   return ret;
}

Каждый раз, когда вы выполняете n&=(n-1), вы удаляете последний бит в n. Таким образом, это время O (количество установленных бит).

Это быстрее, чем O (log n), который вам понадобится, если вы будете тестировать каждый бит - не каждый бит установлен, если только число 0xFFFFFFFFFFFFFFFF), поэтому обычно вам нужно гораздо меньше итераций.

Ответ 3

Стандартный ответ в С#:

ulong val = //whatever
byte count = 0;

while (val != 0) {
    if ((val & 0x1) == 0x1) count++;
    val >>= 1;
}

Это сдвигает val вправо один бит и увеличивает count, если установлен самый правый бит. Это общий алгоритм, который может использоваться для любого целого числа.