Число количества битов в 64-разрядном (длинный, большой) целое число?
Я прочитал это ТАК вопрос приблизительно 32 бита, но что относительно 64-разрядных чисел? Я должен просто замаскировать верхние и более низкие 4 байта, выполнить количество на 32 битах и затем добавить их вместе?
3 ответа
Вы можете найти 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);
}
РЕДАКТИРОВАТЬ : Я обнаружил ошибку при тестировании 32-битной версии. Я добавил недостающие скобки. Суммирование должно производиться перед побитовым &, в последней строке
EDIT2 Добавлена более безопасная версия для ulong
Быстрый (и более переносимый, чем использование нестандартных расширений компилятора) способ:
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), таким образом, обычно вам нужно гораздо меньше итераций.
Стандартный ответ в C #:
ulong val = //whatever
byte count = 0;
while (val != 0) {
if ((val & 0x1) == 0x1) count++;
val >>= 1;
}
Это сдвигает val на один бит вправо и увеличивает count , если установлен крайний правый бит. Это общий алгоритм, который можно использовать для целых чисел любой длины.