Грокаем C++

Считаем единички. Решения

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

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. Нахождение количества единичных бит в числе - это не просто задача с литкода. У нее есть практическое применение. Есть такая штука, как расстояние Хемминга для двоичных чисел. Это количество символов, которое отличает данную строку битов от строки, заполненной нулями. То есть это и есть наше количество единичек. Эта штука используется во многих дисциплинах, в том числе и криптографии. Не удивительно, что много народу совершенствовало решение этой задачи. На мой взгляд, самое мозгодробительное решение выглядит примерно так:

❤10👍7⚡4🔥2🤔1😱1

5.23K views14:59