Задача

Для N змінних типу bool треба знайти всі варіанти комбінацій їх значень.

Рішення

Ідея полягає в тому що після того як змінено значення однієї змінної в true (починаємо з останньої) встановлюємо усі що йдуть за нею в false. Кожна наступна ітерація починає з останнього зміненого значення.

   1:      bool* vals = new bool[N];
   2:      for (int i = 0; i < N; ++i) vals[i] = false;
   3:   
   4:      bool cont = true;
   5:      while (cont)
   6:      {
   7:          for (int j = 0; j < N; ++j) 
   8:          {
   9:              cout << (vals[j] ? "t" : "f") << ", ";
  10:          }
  11:          cout << 'b' << endl;
  12:   
  13:          cont  = false;
  14:   
  15:          for (int i = N - 1; i >=0; --i)
  16:          {
  17:              if (!vals[i])
  18:              {
  19:                  vals[i] = true;
  20:                  cont = true;
  21:   
  22:                  for (++i; i < N; ++i) vals[i] = false;
  23:   
  24:                  break;
  25:              }
  26:          }
  27:      }
  28:   
  29:      delete [] vals;

Оптимізація

Абсолютно зайвим є витрачання цілого байта на значення яке може буте збереженим в одному біті. Тож можна об’єднати 8, або навіть більше значень в одному.

   1:  template <class T>
   2:  unsigned getBit(size_t index, T* storage, size_t size)
   3:  {
   4:      auto position = index / (sizeof(T) * CHAR_BIT);
   5:      auto bit = index % (sizeof(T) * CHAR_BIT);
   6:      
   7:      return (storage[size - position - 1] >> bit) & 1;
   8:  }
   9:   
  10:  typedef unsigned char storageType;
  11:  const int bitsInPosition = sizeof(storageType) * CHAR_BIT;
  12:   
  13:  ...
  14:      auto positions = N / bitsInPosition;
  15:      if (N % bitsInPosition > 0) ++positions;
  16:      storageType* vals = new storageType[positions];
  17:      auto mask0Position = (1 << (N % bitsInPosition)) - 1;
  18:   
  19:      for (auto i = 0; i < positions; ++i) vals[i] = 0;
  20:   
  21:      for (size_t i = positions - 1; ;)
  22:      {
  23:          for (size_t j = 0; j < N; ++j) 
  24:          {
  25:              cout << getBit(j, vals, positions);
  26:          }
  27:          cout << endl;
  28:   
  29:          if ((++vals[i] == 0) ||
  30:              (i == 0 && ((vals[0] & mask0Position) == 0)))
  31:          {
  32:              if (i == 0)
  33:              {
  34:                  break;
  35:              }
  36:              
  37:              while (++vals[--i] == 0);
  38:              i = positions - 1;
  39:          }
  40:      }
  41:   
  42:      delete [] vals;
  43:  

Задача

Написати найефективнішим способом функцію що для заданого x повертає таке число n що 2^(k-1) <= n < 2^k. Ішими словами функція має повертати наступну за заданим числом ступінь двійки.

Рішення

Ідея полягає в тому щоб розкопіювати найстаршу одиницю в усі біти і додати 1 – так ми отримаємо наступну ступінь двійки. Хоча ми і не знаємо де наступна одиниця, проте можемо зробити наступне (для 4-байтового значення):

1. копіюємо старші 2 біти в молодші – тепер у нас 2 копії найстаршої одиниці

2. зверху накладаємо ті самі біти але зсунуті на один байт вправо – маємо 4 копії

3. зверху накладаємо ті ж біти але зсунуті на 4 біти вправо – маємо 8 копій

4. повторюємо для зсува в 2 і 1 біт – маємо найстаршу одиницю встановлену у всих наймолодших бітах

5. додамо 1 – маємо наступну ступінь двійки, бо це буде лише одна одиниця на всі біти.

Рішення не враховує переповнення.

int NearestPowerOf2(int x) 
{
    –x;   
     x |= x >> 1;
    x |= x >> 2;    
    x |= x >> 4;    
    x |= x >> 8;    
    x |= x >> 16;    
    return ++x;
}

Визначити скільки біт (двійкових розрядів) треба відвести під те, щоб записати число 53²⁰⁶⁷?

Рішення:

Оскільки 2ⁿ=n біт, тож рішенням буде нерівність

2^n-1< 53²⁰⁶⁷ <=2ⁿ                          –                      логарифмуємо за основою 53, маємо

(n-1) log₅₃2<2067<=n log₅₃2,                            де log₅₃2= 0,1745,

тож

n-1<2067/0.1745<=n,                                          тобто n-1<11839.61<=n.

Oоп-ля (:

Логарифмування! обожнюю (:

Задача

Що перевіряє умова ((n & (n – 1) == 0) для цілих чисел?

Рішення

Для будь-яких чисел A та B операція A & B даватиме 0 якщо в них не співпадає жоден біт.

За яких умов у n та (n – 1) не співпадатиме жоден біт? Таке можливо тільки коли у n встановлено лише один біт. Наприклад:

Як бачимо результат операції є нульовим лише коли встановлено один біт числа, або іншими словами коли число є ступенем двійки.

Задача

Для цілого числа знайти найближче до нього більше число в якому така сама кількість встановлених в 1 бітів.

Рішення 1

Спочатку знайдемо (зправа наліво) перший нульовий біт який можна встановити в 1. Щоб число було більше знаходимо перший нульовий біт який йде за першою одиницею чи групою одиниць.

Встановлюємо знайдений біт в 1, а попередній ненульовий біт в 1. Далі треба зсунути усі попередні ненульові біти до самого початку.

unsigned get_next_n(unsigned n)
{
    if (n == 0) return 0;

    unsigned idx = 0, bits = 0;

    // find 1st 1
    while ((n & (1 << idx)) == 0) ++idx;

    // find 1st 0 after 1
    while (n & (1 << idx)) ++idx, ++bits;

    // set 0 to 1
    n |= 1 << idx;

    // set previous bits to minimal possible value - 
    // all 1s at the very beginning
    --bits;
    int zeroMask = ~((1 << idx) - 1);
    n &= zeroMask;

    int onesMask = (1 << bits) -1;
    n |= onesMask;

    return n;
}

Для пошуку найближчого меншого числа з такою ж кількістю встановлених бітів міняємо всі умови на протилежні. Тобто знаходимо перший встановлений біт після першої групи нулів, міняємо його на 0, а усі інші встановлені біти зсовуємо справо до знайденої позиції.

unsigned get_prev_n(unsigned n)
{
    if (n < 2) return 0;

    unsigned idx = 0, bits = 0;

    // find 1st 0
    while (n & (1 << idx)) ++idx, ++bits;

    // find 1st 1 after 0
    while ((n & (1 << idx)) == 0) ++idx;

    // set 1 to 0
    n &= ~(1 << idx);

    // set previous bits to maximal possible value - 
    // all 1s right aligned at idx position
    ++bits;
    int zeroMask = ~((1 << idx) - 1);
    n &= zeroMask;

    int onesMask = ((1 << bits) - 1) << (idx - bits);
    n |= onesMask;

    return n;
}

Рішення 2

Більш складне рішення для розуміння якого треба знати як представлені у двійковому вигляді від’ємні числа.

Візьмемо для прикладу число x = 76. Також представимо що усе знакове число у нас (для простоти) є однобайтним.

x = 01000110

Від’ємні числа представлені так – усі байти інфертовано плюс одиниця. Таким чином –1 преставлено як 11111111, –2 – 11111110 і так далі.

-x = 10111010

Бачимо що у x та –x співпадають лише перші ненульові біти. Отже можемо виділити цей біт:

x & –x = 00000010

Якщо до оригінального числа додати цей перший ненульовий біт то встановимо в одиницю перший нульовий біт що йде після першої одиниці (чи групи одиниць), а всі молодші біти встановимо в 0. Це буде ліва частина числа:

x + (x & –x) = 01001000

Тепер, якщо порівняти оригінальне число і отриманий результат бачимо що неспівпадають молодші біти. Можемо виділити лише їх:

x ^ (x + (x & –x)) = 00001110

Ці біти треба зсунути до самого початку числа і прибрати один зайвий. Отримуємо праву частину числа:

(x ^ (x + (x & –x))) >> 2) / (x & –x) = 00000001

Об’єднуємо ліву і праву частини:

((x ^ (x + (x & –x))) >> 2) / (x & –x)) | (x + (x & –x)) = 01001001

В коді це виглядатиме так:

unsigned get_next_n(unsigned n)
{
    unsigned firstBit = n & -n;
    unsigned leftPart = n + firstBit;
    
    unsigned rightPart = 
        ((n ^ leftPart) >> 2) / firstBit;
    
    return leftPart | rightPart
}

Пояснення цього метолу зі слайдами тут – http://www.slideshare.net/gkumar007/bits-next-higher-presentation

Задача

Дано два 32-розрядних числа M та N, а також позиції i та j. Розмістити значення N у бітах від i до j числа M.

Ріщення

Побудуємо маску яка обнулить біти від i до j 32-х розрядного чила, після чого обнуломо відповідні біти в M і скопіюємо в них N:

int max = ~0; // усі біти встановимо в 1
// усе зправа від j встановимо в 0
int left = max - ((1 << j) - 1); 
// усе зліва від i встановимо в 0
int right = (1 << i) - 1;
// у масці біти від i до j встановлені у 0, всі інші - в 1
int mask = left | right;

// обнуляємо біти в M
M &= mask;
// копіюємо біти з N в M
M |= N << i;

Задача

Для цілого числа (для спрощення візьмемо unsigned int) підрахувати кількість ненульових бітів у ньому найефективнішим способом.

Рішення

Кожен біт вже містить кількість ненульових бітів у ньому – це або 0, або 1

Для кожної пари бітів сума їх значень дорівнює кількості ненульових бітів у цій парі. Причому це може бути 0, 1, або10 (у двійковій системі). Тобто результат поміщується у ті самі біти.

Сума значень пар дорівнює кількості ненульових бітів у 4-бітних фрагментах. І так далі.

int nonZeroBits(unsigned int x)
{
  // 2 bits sums
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

  // 4 bits sums
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);

  // 8 bits sum
  x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);

  // 16 bits sum
  x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff)

  // and sum for all 32 bits
  x = (x & 0x0000ffff) + (x >> 16);

  return x;
}