ДЗ 3. Битовые операции

Задача 1.

Сначала поменяем местами каждый бит с соседом, потом каждый кусочек по два бита с соседом, и так далее. В конце вернем 1, если рузельтат равен исходному числу, иначе 0.

int palindrome (uint64_t x) {
  uin64_t mask1 = 0x5555555555555555,
          mask2 = 0x3333333333333333,
          mask3 = 0x0f0f0f0f0f0f0f0f,
          mask4 = 0x00ff00ff00ff00ff,
          mask5 = 0x0000ffff0000ffff,
          mask6 = 0x00000000ffffffff,
          meow  = x;

  meow = ((x & mask1)    << 1)  | ((x & (mask1 << 1)) >> 1));
  meow = ((meow & mask2) << 2)  | ((x & (mask2 << 2))  >> 2));
  meow = ((meow & mask3) << 4)  | ((x & (mask3 << 4))  >> 4));
  meow = ((meow & mask4) << 8)  | ((x & (mask3 << 8))  >> 8));
  meow = ((meow & mask5) << 16) | ((x & (mask5 << 16)) >> 16));
  meow = ((meow & mask6) << 32) | ((x & (mask6 << 32)) >> 32));

  return !(x - meow);
}

Задача 2.

Можем делить числа x и y на два отдельно, чтобы избежать переполнения при сложении. Но тогда потеряем 1, если оба числа нечетные, так что его надо добавить в конец.

uint32_t mean (uint32_t x, uint32_t y) {
  return (x >> 1) + (y >> 1) + ((x & 1) & (y & 1));
}

Задача 3.

Посмотрим на знаковый бит разности. Если он единичный, значит a<b, иначе наоборот. Далее используем чуть-чуть branchless программирования

uint32_t max (uint32_t a, uint32_t b) {
  int32_t diff = (a - b);
  int32_t a_is_smaller = (diff >> 31); // 0xFFFFF.... if a < b
  return (a + (b - a) & a_is_smaller); // a + (b - a) if a < b, else a
}

Задача 5.

1. Выставляет все биты левее самого младшего нулевого бита, остальные обнуляет

2. Выставляет все биты правее самого младшего единичного бита, остальные обнуляет

3. Выставляет самый правый нулевой бит

4. Выставляет все нулевые биты, после которых нет единичных

5. Выделяет самый младший единичный бит