Пункт 6

Хранение целых чисел в памяти

Целые числа представляются таким образом (для 64-битных чисел):

• В двоичной системе счисления для чисел от 0 до 263-1

• В дополнительном коде для отрицательных чисел от -1 до -263

Обратный код: все биты числа перевернуты

Дополнительный код: к обратному коду добавляется единица

Удобно это все дело тем, что все операции в дополнительном коде работают точно также, как и в обычном, и в итоге знаки получаются правильными (если переполняющийся старший бит просто игнориоровать)

Полусумматор и сумматор

Полусумматор - схема, которая принимает в себя два однобитных числа, и выдает два однобитных - сумма чисел по модулю два и перенос. Таблица истинности:

Это соответствует формулам: S=A⨧B,C=A∧B:

Сумматор или полный сумматор: схема, которая складывает два числа и бит переноса, и выдает сумму и бит переноса:

Такую схему можно составить из двух полусумматоров (half-adder это прошлая схема):

Или, расписывая напрямую:

Такие сумматоры можно соединять, запихивая C в P следующего разряда, и получать многоразрядные сумматоры. Вот, например, четырехбитный сумматор:

Алгоритм Брайана-Кернигана. Подсчет единичных бит.

Собственно говоря, алгоритм Брайна Кернигана (у меня есть подозрение, что это один человек, хых):

int ctz (unsigned int n) {
  int result = 0;
  while (n) {
    n &= n - 1;
    result++;
  }

  return result;
}

Асимтотика: O(m), где m - количество единичных бит

TODO

еще куча алгоритмов: https://habr.com/ru/articles/276957/