Давайте быстро пробежимся через самое банальное решение. Нужно в цикле проверять по маске последний бит числа и сдвигать его вправо, пока число не превратится в ноль.
int count_ones(unsigned num) {
int result = 0;
while(num > 0) {
result += num & 1;
num >>= 1;
}
return result;
}Алгоритмическая сложность этого решения - О(log(num)).
Что может быть интереснее? Например, знали ли вы, что выражение num & (num - 1) лишает число его самой правой единички? Посмотрите сами:
10 = 1010
1010 & (1010 - 1) = 1010 & 1001 = 1000
118 = 111011
111011 & (111011 - 1) = 111011 & 111010 = 111010
Поэтому в цикле, вместо сдвига числа вправо можно просто бинарно умножать число на это же число, уменьшенное на единицу. Даже считать отдельно ничего не нужно, количество итераций цикла определять число единичек. Это кстати в среднем в 2 раза эффективнее, чем просто каждый раз смотреть последний бит числа, но ассимптотическую сложность не меняет. Ну и для любителей кода покороче, все это можно написать так:
int count_ones(unsigned num) {
int result = 0;
for(; num > 0; num &= (num - 1), ++result);
return result;
}А что насчет самого короткого решения? Зачем писать велосипед, если можно просто воспользоваться встроенной функцией компилятора(или С++20 фичей):
int count_ones(unsigned num) {
return std::popcount(num);
// or compiler extension
// return __builtin_popcount(num);
}А что, если мы хотим константную сложность? Такое вообще возможно?
Конечно. Нам потребуется всего sizeof(num)* 8 итераций цикла и проверки последнего бита, чтобы найти нужное число. Константа? Да. Эффективно ли это? Это даже медленнее, чем самое первое решение.
Однако давайте подумаем еще чуть-чуть. Комбинаций битов в инте на самом деле не такой уж и и много. Всего 2^32. Можно создать массив байтов на 2^32 элементов и в каждой ячейке хранить количество единичек для числа равного индексу этой ячейки. Мы это как-то можем заранее нагенерить(или при первом вызове функции) и потом все вызовы функции count_ones будут занимать константное время. Правда памяти сожрется на это предостаточно.
static std::array<uint8_t, std::numeric_limit<uint32_t>::max()> ones;
// somehow fill array
int count_ones(unsigned num) {
return ones[num];
}
Кстати полезный ход. Иногда из-за сильных ограничений по входным данным задачи ее можно решить намного более оптимальным способом.
Если боитесь больших массивов, то можно немного схитрить. Мы можем запомнить в таблице количество единиц для каждого возможного байта, разбить число на 4 части, найти для этих частей количество хранящих в них единичек по таблице и сложить это дело. Получится, что нужно всего 256 байт доп памяти и 4 итерации цикла.
Но чтобы было прям наглядно понятна логика, то массив можно сделать еще меньше, если брать по 4 бита(тетрад). Различных тетрадов всего 16 штук, поэтому и нужно будет всего 16 байт доп памяти и 8 итераций цикла. Спасибо, @tutralex, за решение)
int count_ones(unsigned num)
{
static unsigned char c[16]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
int count=0;
while (num)
{
count+=c[num&0x0F];
num>>=4;
}
return count;
};
В общем, вы поняли. Чем меньше массив, тем больше итераций цикла и наоборот. Выбирайте, что вам больше подходит.
Если вы еще не устали, то у меня для вас есть banger. Нахождение количества единичных бит в числе - это не просто задача с литкода. У нее есть практическое применение. Есть такая штука, как расстояние Хемминга для двоичных чисел. Это количество символов, которое отличает данную строку битов от строки, заполненной нулями. То есть это и есть наше количество единичек. Эта штука используется во многих дисциплинах, в том числе и криптографии. Не удивительно, что много народу совершенствовало решение этой задачи. На мой взгляд, самое мозгодробительное решение выглядит примерно так: