Младший единичный бит так вроде?
((a^(a-1))+1)>>1

Вариант покрасивее:
(a^(a-1))&a

Является ли число степенью двойки?

Проверка неполна: надо еще проверить, что v ≠ 0. Более того, стоит отдельно указать, что происходит в знаковых переменных (например, иногда — undefined behavior на плюсах).

обменять значения переменных, не использую третью переменную с помощью XOR.

Только не надо, пожалауйста, учить людей undefined behavior без указания того, к чему это может привести (aka писать "в одну клёвую команду").

По делу (если что-то из этого вам непонятно, могу расписать):

1. Битовые маски — храним подмножества множества из 32/64/128 фиксированных элементов. Каждый бит — есть элемент или нет. Дополнение (~, не !), пересечение (& и &=), объединение (|, |=), установка бита по номеру (| 1 << x), снятие бита по номеру (& ~(1 << x)), сдвиги влево-вправо (стоит сделать замечание про знаковость в плюсах и про >>> в Java).
2. Подсчёт количества единиц в числе за (где w — разрядность) методом "разделяй и властвуй". Обычно работает медленнее предподсчёта, но надо сравнивать
3. Перебор всех над/подмножеств множества за O(Ans) одним циклом for. В частности — перебор всех пар "множество/его подмножество" за O(3ⁿ).
4. Дерево Фенвика: какое было изначально определение, как и в какие формулы оно сворачивается
5. Для GCC: __builtin_popcount, __builtin_ctz, __builtin_clz и прочая, прочая, прочая (в том числе с суффиксами ll).
6. Кодирование кортежей из небольших чисел (например, 0-3) в битмаске: установить значение i-го элемента, получить и так далее.
7. Два способа получения значения бита: (a >> x) & 1 и a & (1 << x), чем отличаются. Если в плюсах писать внутри условия if, то ничем. А вот если пытаться немедленно использовать результат операции внутри другой, то возможны варианты: первая штука возвращает 0/1, а вторая — 0/x-ый бит, в разных местах нужно разное.
8. Битовое сжатие: алгоритм Флоида за и std::bitset
9. Выражение сложения через O(w) битовых операций: просто на каждом шагу считаем отдельно XOR и перенос. Вроде можно еще за битовых операций (надо научиться быстро считать переносы при помощи этакого дерева отрезков).
10. Определение знака целого числа взятием старшего бита.
11. Низкий приоритет у ^ и << в плюсах по сравнению с некоторыми другими операциями (например, сравнениями или сложениями).
12. Быстрое приближение обратного квадратного корня.

Еще можно загуглить и получить вот это. Пара вещей оттуда (не проверял):

1. Определить, имеют ли целые числа разные знаки: (x ^ y) < 0.
2. Подсчёт числа бит в 14-битном значении через умножение на многочлен в кольце : (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

Поищи книгу Алгоритмические трюки для программистов, там полно трюков с битовыми операциями.

По множеству масок посчитать все маски, которые содержат хотя бы одну из них:

for (int mask : v)
    dp[mask >> 5] |= (1 << (mask & 31));

for (int mask = 0; mask < (1 << (let - 5)); mask++)
{
    dp[mask] |= (dp[mask] & 0x0000ffff) << 16;
    dp[mask] |= (dp[mask] & 0x00ff00ff) << 8;
    dp[mask] |= (dp[mask] & 0x0f0f0f0f) << 4;
    dp[mask] |= (dp[mask] & 0x33333333) << 2;
    dp[mask] |= (dp[mask] & 0x55555555) << 1;

    for (int j = 0; j < let - 5; j++)
        dp[mask | (1 << j)] |= dp[mask];
}

Смысл состоит в том, что мы храним по 2⁵ значений динамики "удовлетворяет ли названному условию?" в каждом элементе массива, таким образом биты int-ов соответствуют последним 5 битам маски, номер в массиве оставшимся битам. Переходы по "внешним" битам тривиальны, а по "внутренним" выражаются с помощью битовых операций.

P. S. Константы в двоичной записи выглядят так: 00000000000000001111111111111111, 00000000111111110000000011111111, 00001111000011110000111100001111, 00110011001100110011001100110011, 01010101010101010101010101010101, то есть мы выделяем среди наших состояний те, в которых нет 4-го, 3-его, 2-го, 1-го, 0-го битов и делаем из них соответствующие переходы.

Zero is not a power of two. Your code says otherwise :)

Я верю в то, что битовые трюки за меня делает -O2 :)

Например, https://en.wikipedia.org/wiki/Hamming_weight

Если что, пункт 9 из списка Егора уже есть в вики-конспектах. Правда, на мой вкус, там не слишком понятное описание.

Минимум среди (x, y) = y ^ ((x ^ y) & -(x < y))
Когда x<y: y ^ ((x ^ y) & -(x < y)) = y ^ ((x ^ y) & -1) = y ^ (x ^ y) = x
Когда x>y: y ^ ((x ^ y) & -(x < y)) = y ^ ((x ^ y) & 0) = y ^ 0 = y

or:
f = __builtin_popcount(v) == 1;

Всё написано до нас: link

Smallest bit set to 1 of an integer

int bit = number & -number;

Explanation: -number representation using 2-complement keeps the smallest 1-bit and inverts the other most significative bits.

Unsetting the smallest 1-bit of an integer

int number = 123; number -= number & -number;

Counting the number of bits set to 1

int amount = 0;
for (; number > 0; number -= number & -number)
  ++amount;

Toggle bit i from 1->0 or 0->1

number ^= 1 << i;

Xor with bit set to 1, makes it change its value, whereas the other bits are 0 and don't change anything.

Iterate all subsets of a bitmask in increasing order

for ( int sub = 0 ; sub = sub - bitmask & bitmask ; ) {
  // do something
}

Iterate all subsets of a bitmask in decreasing order

for(int sub = (mask-1) & bitmask ; sub > 0 ; sub = (sub-1) & bitmask )  {
  // do something 
}

Один из классических рюкзаков, а точнее Subset sum problem, на битсетах:

bitset<MAXS> d;
d[0] = 1;
int n;
cin >> n;
while (n--) {
    int x;
    cin >> x;
    d |= d << x;
}
int s;
cin >> s;
cout << d[s] << endl;

И работает быстро, и пишется просто.

Оставлю тут pdf

Из того, о чём ещё не писали, там, например, есть рюкзак с восстановлением ответа и Гаусс.

Задача для затравки: Найти младший единичный бит за O(1)

А номер младшего за O(1) умеешь? ;)

Swap two integers

a ^= b ^= a ^= b;

Check whether two integers are equal or not:

if (a ^ b) // they aren't equal!

Check if a equals -1 or not

if (~a) // a != -1

Get the largest number I can!

int (or long long) INF = -1ull/2;

For the least number

int (or long long) LEAST = ~(-1ull/2);

Operation x & (x — 1) sets rightmost 1 to 0. As powers of 2 have only one 1 — it can be used to check them.

My favorite is binary searching by bit manipulation — no off-by-1 errors!

/**
   * Binary search by bit toggling from MSB to LSB
   * O(64) bit-wise operations for Longs (O(32) for Ints)
   *
   * @return Some(x) such that x is the largest number for which f is true
   *         If no such x is found, None
   */
  def bitBinSearch(f: Long => Boolean): Option[Long] = {
    var p = 0L
    var n = Long.MinValue
    var t = n >>> 1
    while (t > 0) {
      if (f(p|t)) p |= t
      if (f(n|t)) n |= t
      t >>= 1
    }
    Seq(p, n) find f
  }

Original source: https://github.com/pathikrit/scalgos/tree/master/src/main/scala/com/github/pathikrit/scalgos

Дико прошу прощения, если мой коммент покажется неконструктивным, но опасаюсь, как бы вся Ваша статься не получилась ещё более неконструктивной.

Такие вещи позволительно писать только когда есть чёткое описание возможных подвохов. Хотя бы тот же классический обмен двух переменных без третьей — по моему глубокому убеждению, надо либо обязательно указывать, что оно работает только при &x!=&y (а при &x==&y приводит к утрате значения этой переменной), либо вообще не рассказывать о таком! И это касается не только конкретно обмена, а вообще всего.

Can someone provide links to the problems, where you need a fast way to count number of 1's in mask or index of last setted bit?