Bit Operations

• Bit Manipulation
• Extended De Morgan’s Laws
• Next Higher Number with Same Number of 1-bits
• Algorithmic & Mathematical Operations
• x >= 0 ? 1 : -1
• x == a ? b : a
• Average of Two Integers Without Causing Overflow
• Power of 2
• Reversing Bits
• Reference

Bit Manipulation

• x & (x - 1) — turn off the rightmost 1-bit, producing 0 if none
  • e.g. 01011000 -> 01010000
  • determine if an unsigned integer is a power of 2 or is 0
• x | (x + 1) — turn on the rightmost 0-bit, producing all 1’s if none
  • e.g. 10100111 -> 10101111
• x & (x + 1) — turn off the trailing 1’s, producing x if none
  • e.g. 10100111 -> 10100000
  • determine if an unsigned integer is of the form $2^n - 1$, 0, or all 1’s
• x | (x - 1) — turn on the trailing 0’s, producing x if none
  • e.g. 10101000 -> 10101111
• ~x & (x + 1) — turn off all but turning on the rightmost 0-bit only, producing 0 if none
  • e.g. 10100111 -> 00001000
• ~x | (x - 1) — turn on all but turning off the rightmost 1-bit only, producing all 1’s if none
  • e.g. 10101000 -> 11110111
• ~x & (x - 1), ~(x | -x), or (x & -x) - 1 — turn off all but turning on the trailing 0’s only, producing 0 if none
  • e.g. 01011000 -> 00000111
  • ~x & (x - 1) has some instruction-level parallelism
• ~x | (x + 1) — turn on all but turning off the trailing 1’s only, producing all 1’s if none
  • e.g. 10100111 -> 11111000
• x & (-x) — turn off all but the rightmost 1-bit only, producing 0 if none
  • e.g. 01011000 -> 00001000
• x ^ (x - 1) — turn off all but turning on the trailing 0’s including the rightmost 1-bit, producing all 1’s if no 1-bit, and the integer 1 if no trailing 0’s
  • e.g. 01011000 -> 00001111
• x ^ (x + 1) — turn off all but turning on the rightmost 0-bit including the trailing 1’s, producing all 1’s if no 0-bit, and the integer 1 if no trailing 1’s
  • e.g. 01010111 -> 00001111
• ((x | (x - 1)) + 1) & x or ((x & -x) + x) & x — turn off the rightmost contiguous 1’s
  • e.g. 01011100 -> 01000000
  • determine if a nonnegative integer is of the form $2^j - 2^k$ for some $j \geq k \geq 0$

Extended De Morgan’s Laws

Other than the original De Morgan’s Laws such as ~(x & y) = ~x | ~y and ~(x | y) = ~x & ~y, this idea can be extended further.

• ~(x + y) == ~x - y
• ~(x - y) == ~x + y
• ~(x ^ y) == ~x ^ y
• ~(-x) == x - 1

From these facts, addition can be combined with logical operations.

• -x == ~(x - 1) == ~x + 1
  • -(~x) == x + 1
• x + y == x - (-y) == x - (~y + 1) == x - ~y - 1
  • x + y == (x ^ y) + ((x & y) << 1)
    • This computes the sum without carries first, and then adding carries. Note that the left shift is used since carries should be applied to the left bit of each.
  • x + y == (x | y) + (x & y)
    • Let y0 be a variable with 0-bit if a bit of y and the corresponding bit of x are the same as 1, and the same bit with y otherwise. Also, let y1 = x & y. Then, y == y0 + y1. So, x + y == x + (y0 + y1) == (x + y0) + y1 == (x | y) + (x & y).
• x - y == x + (-y) == x + (~y + 1) == x + ~y + 1
  • x - y == (x ^ y) - ((~x & y) << 1)
    • This computes the subtraction without borrows first, and then subtracting borrows. Note that the left shift is used since borrows should be applied to the left bit of each.
  • x - y == (x & ~y) - (~x & y)
    • Let $(x_i, y_i)$ be the $i$-th bit-pair of x and y. Now, let x0 and y0 be variables with each $x_i$’s and $y_i$’s at the positions if $(x_i, y_i) = (1, 0)$, and with 0’s otherwise. Similarly, x1 and y1 have $x_i$’s and $y_i$’s from the pairs $(x_i, y_i) = (0, 1)$, x2 and y2 from $(x_i, y_i) = (1, 1)$, and x3 and y3 from $(x_i, y_i) = (0, 0)$. Then, x = x0 + x1 + x2 + x3 and y = y0 + y1 + y2 + y3. So, x - y = (x0 - y0) + (x1 - y1) + (x2 - y2) + (x3 - y3) = (x0 - y0) + (x1 - y1) = (x0 - y0) - (y1 - x1) == (x & ~y) - (~x & y).
• x ^ y == (x | y) - (x & y)
• x | y == (x & ~y) + y
• x & y == (~x & y) - ~x

Next Higher Number with Same Number of 1-bits

When bit strings are used to represent subsets, finding the next higher number with the same number of 1-bits might help to iterate through all the subsets. The idea to solve this problem is to find the rightmost contiguous group of 1’s in x and the following 0’s, and increment that quatity to the next value that has the same number of 1’s.

unsigned int findNextHigherNumber(unsigned int x)
{
                                         // e.g. x = ???0 1111 0000
   unsigned int smallest = x & -x;       //          0000 0001 0000
   unsigned int ripple = x + smallest;   //          ???1 0000 0000
   unsigned int ones = x ^ ripple;       //          0001 1111 0000
   ones = (ones >> 2) / smallest;        //          0000 0000 0111
   return ripple | ones;                 //          ???1 0000 0111
}

Algorithmic & Mathematical Operations

• (x - y) & -(x >= y) — saturation, or std::max( x - y, 0 )
  • For signed integers, the result can be negative, which means overflow in the subtraction. But, this negative result is actually the correct difference if it is interpreted as an unsigned integer.
  • Let this operation be the function f(x, y). Then, f(~x, ~y) == f(y, x).
• (x ^ y) & -(x >= y) ^ y — std::max( x, y )
• (x ^ y) & -(x <= y) ^ y — std::min( x, y )
• ((x - y) & -(x >= y)) + ((y - x) & -(y >= x)) — std::abs( x - y )
• ~((~x - y) & -(~x >= y)) — clamp the sum of unsigned integers x and y to the maximum positive integer $2^{32} - 1$

• selective swap
  • swap with a mask m

    x = x ^ y;
    y = y ^ (x & m);
    x = x ^ y;
    

  • swap by chunk with a mask m

    // swap B and D with m (the sizes of B & D must be the same)
    //                |-- k-bit --|
    // x: |  A  |  B  |  C  |  D  |  E  |
    // m: |        0        | xxx |  0  |
    a = (x ^ (static_cast<unsigned int>(x) >> k)) & m;
    b = a << k;
    swapped = x ^ a ^ b;
    

x >= 0 ? 1 : -1

(x >> 30) | 1 is the statement to obtain the sign value of a 32-bit signed integer without any branch statement. If 0 must be returned when x == 0 for some reason, the right workaround are as follows.

int signWithFourInstructions(int x)
{
   // -1 (x < 0), 0 (x == 0), 1 (x > 0)
   return (x >> 31) | (static_cast<unsigned int>(-x) >> 31)
}

int signWithThreeInstructions(int x)
{
   // -1 (x < 0), 0 (x == 0), 1 (x > 0)
   return (x > 0) - (x < 0)
}

In general, signWithThreeInstructions() can be extended into the comparison of two integers. Note that in this case both unsigned and signed integers are supported.

template<typename T>
concept integer_type = std::same_as<int, T> || std::same_as<unsigned int, T>;

template<typename T>
requires integer_type<T>
T compare(T x, T y)
{
   // -1 (x < y), 0 (x == y), 1 (x > y)
   return (x > y) - (x < y);
}

x == a ? b : a

As a short example, for both unsigned and signed integers a and b, suppose x should be set alternating among a or b. In this case, a + b - x or a ^ b ^ x is a far better way to do this. Overflow in calculating a + b can be ignored.

Average of Two Integers Without Causing Overflow

For two integers x and y, there is a well-known technique to calculate the average of them without overflow if which one is larger has been already known. x + (y - x) / 2 works with both unsigned and signed integers and calculates floor averages. What if, however, which one is larger has been unknown? It may be still fine if min() and max() functions are used. But, there are other techniques to do this without any branch statement. They even work with ceiling averages as well as floor averages.

template<typename T>
concept integer_type = std::same_as<int, T> || std::same_as<unsigned int, T>;

template<typename T>
requires integer_type<T>
T calculateFloorAverage(T x, T y)
{
   // e.g. x = 0, y = -1 -> -1
   //      x = 0, y = +1 -> 0
   return (x & y) + ((x ^ y) >> 1);
}

template<typename T>
requires integer_type<T>
T calculateCeilingAverage(T x, T y)
{
   // e.g. x = 0, y = -1 -> 0
   //      x = 0, y = +1 -> 1
   return (x | y) - ((x ^ y) >> 1);
}

Sometimes, truncated average is required for signed integers. In this case, the additional correction part is needed after the floor average. The correction is add 1 if x + y is negative and odd.

int calculateTruncatedAverage(int x, int y)
{
   // e.g. x = 0, y = +2 -> 1
   //      x = 0, y = +1 -> 0
   //      x = 0, y = -1 -> 0
   //      x = 0, y = -2 -> -1
   int t = (x & y) + ((x ^ y) >> 1);
   return t + ((static_cast<unsigned int>(t) >> 31) & (x ^ y));
}

Power of 2

• x & -(1 << n) — the next smaller multiple $2^n$ for an unsigned integer x, producing x if x is already a multiple $2^n$
  • The maximum of $2^n$ is the number of bits of the type of x.
• x + (-x & ((1 << n) - 1)) — the next greater multiple $2^n$ for an integer x, producing x if x is already a multiple $2^n$
  • The maximum of $2^n$ is the number of bits of the type of x.
  • ((1 << n) - 1) is a constant if n is fixed.
  • (-x & ((1 << n) - 1)) is useful when it is needed to know how much exactly must be added to x.
  • If the rounding up in the positive direction is valid even for negative values, this expression is correct for signed integers.
    • if n == 3 and x == -7, then the result is 0.
    • if n == 3 and x == -8, then the result is -8.
    • if n == 3 and x == -9, then the result is -8.
• Rounding up/down to the next power of 2 for a 32-bit unsigned integer x
  • In the following code, __builtin_clz() is a built-in function to get the number of leading zeros.

  unsigned int roundDownWithCLZ(unsigned int x)
  {
    // must be x > 0
    return 1 << (31 - __builtin_clz(x));
  }

  unsigned int roundUpWithCLZ(unsigned int x)
  {
    // must be 1 < x <= 2^(31)
    return 1 << (32 - __builtin_clz(x - 1));
  }

  unsigned int roundDown(unsigned int x)
  {
    // when x == 0, return 0
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x - (x >> 1);
  }

  unsigned int roundUp(unsigned int x)
  {
    // when x == 0 or x > 2^(31), return 0
    x--;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x + 1;
  }

Reversing Bits

Donald E. Knuth suggested the function to reverse 32 or 64 bits with a few instructions and unexpectedly irregular shifting and masking steps.

// 0x003f801f => 0000 0000 0011 1111 1000 0000 0001 1111
// 0x0e038421 => 0000 1110 0000 0011 1000 0100 0010 0001
// 0x22488842 => 0010 0010 0100 1000 1000 1000 0100 0010
unsigned int reverse(unsigned int x)
{
    x = (x << 15) | (x >> 17);
    unsigned int t = (x ^ (x >> 10)) & 0x003f801f;
    x = (t | (t << 10)) ^ x;
    t = (x ^ (x >> 4)) & 0x0e038421;
    x = (t | (t << 4)) ^ x;
    t = (x ^ (x >> 2)) & 0x22488842;
    x = (t | (t << 2)) ^ x;
    return x;
}

uint64_t reverse(uint64_t x)
{
    x = (x << 32) | (x >> 32);
    x = (x & 0x0001ffff0001ffffll) << 15 | (x & 0xfffe0000fffe0000ll) >> 17;
    unsigned int t = (x ^ (x >> 10)) & 0x003f801f003f801fll;
    x = (t | (t << 10)) ^ x;
    t = (x ^ (x >> 4)) & 0x0e0384210e038421ll;
    x = (t | (t << 4)) ^ x;
    t = (x ^ (x >> 2)) & 0x2248884222488842ll;
    x = (t | (t << 2)) ^ x;
    return x;
}

Reference

[1] Henry S. Warren. 2012. Hacker’s Delight (2nd. ed.). Addison-Wesley Professional.