Bit operations

Bit operations are unary and binary operations on the binary representations of integers. They are divided into two categories: bitwise operations and shifts. Bit operations are among the most basic operations in a CPU, and are often quite fast.

Integers and bit sequences

See also: integer types, complement representation

A fixed-length sequence consisting only of 0 and 1 is called a bit sequence. The leftmost bit is the most significant bit, and the rightmost bit is the least significant bit.

Computers use bit sequences to represent integers in a certain range. A bit sequence of length $N$ has $2^N$ possible forms, so it can correspond one-to-one with $2^N$ integers. These correspondences fall into two categories: signed and unsigned. Signed means that the corresponding integers include negative numbers; unsigned means that all corresponding integers are nonnegative.

• For an unsigned correspondence, we can directly use the binary representation of an integer as the bit sequence, padding the high bits with 0 if it is too short.

  Under an unsigned correspondence, a bit sequence of length $N$ can represent integers in $[0,2^N-1]$.

• For a signed correspondence, there are two representation rules: ones' complement and two's complement.

  For nonnegative integers, the representation rule is the same as for the unsigned case. For negative integers, invert each bit of the bit sequence corresponding to its opposite (changing 0 to 1 and 1 to 0); the result is called the ones' complement. Convert the ones' complement to an integer under the unsigned correspondence, add one, and convert it back to a bit sequence under the unsigned correspondence. Discard any part exceeding the original bit-sequence length; the new sequence is called the two's complement.

  Under the ones' complement correspondence, a bit sequence of length $N$ can represent integers in $[-2^{N-1}+1,2^{N-1}-1]$.

  Under the two's complement correspondence, a bit sequence of length $N$ can represent integers in $[-2^{N-1},2^{N-1}-1]$.

For example, for $3$-bit sequences:

The main problem with ones' complement is that it contains $-0$, a “negative number” that does not actually exist, so in general we use only two's complement. When representing signed integers, the sign is determined solely by the most significant bit of the bit sequence, so this bit is called the sign bit.

Converting a bit sequence to an integer is also easy: for a nonnegative number, no special operation is needed; for ones' complement, invert the bits to obtain the corresponding opposite number; for two's complement, invert the bits and add one to obtain the corresponding opposite number.

Bitwise operations

A bitwise operation applies a Boolean function independently to each bit of a bit sequence. Formally, for a Boolean function $f:\mathbf{B}^k\to \mathbf{B}$, a bitwise operation is a function of the form

where $m$ is the length of the bit sequence. Again, we generally study only unary and binary bitwise operations. Unless otherwise specified, the bitwise operations below are limited to these two cases.

In general, we regard bitwise NOT, bitwise AND, bitwise OR, and bitwise XOR as the basic bitwise operations; all other bitwise operations can be composed from them.

For example:

• $\operatorname{NOT} 01010111=10101000$，
• $01010011 \operatorname{AND} 00110010=00010010$，
• $01010011 \operatorname{OR} 00110010=01110011$，
• $01010011 \operatorname{XOR} 00110010=01100001$．

Since the four bitwise operations above operate independently on each bit, they directly inherit the properties of their corresponding Boolean functions.

For convenience, when the bit-sequence length is known, we can also apply bitwise operations directly to integers, for example:

Assume $x,y\geq 0$. We can also express bitwise operations using sums:

When there is no ambiguity, “bitwise” is omitted below.

Shifts

See also: C++ bitwise operators.

A shift is a binary operation that “moves a bit sequence left or right bit by bit.” Its first argument is a bit sequence, and its second argument is generally a nonnegative integer. Moving left is called a left shift, and moving right is called a right shift. According to how the positions vacated by the shift are filled, shift operations can be divided into arithmetic shifts, logical shifts, and rotations. Specifically:

• Logical shifts fill the empty positions with 0;
• arithmetic right shifts fill the empty positions with the sign bit, while arithmetic left shifts are the same as logical left shifts;
• rotations fill the empty positions with the bits that overflow.

For example, for the $8$-bit sequence 10 01 01 10:

In C++, a << b denotes a left shift and a >> b denotes a right shift; see C++ bitwise operators for the specific shift rules.

A rotation can be implemented with the following code:

// From <https://stackoverflow.com/a/776523/224132>
#include <climits>
#include <cstdint>

uint32_t rotl32(uint32_t value, unsigned int count) {
  const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
  count &= mask;
  return (value << count) | (value >> (-count & mask));
}

uint32_t rotr32(uint32_t value, unsigned int count) {
  const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
  count &= mask;
  return (value >> count) | (value << (-count & mask));
}

Applications of bit operations

Bit operations generally have three uses:

1. Perform certain operations efficiently in place of less efficient methods. See compiler optimizations #strength reduction.
2. Represent sets (often used in state-compression DP).
3. The problem itself requires bit operations.

Note that replacing other operations with bit operations often does not bring much optimization, and may instead make the code more complex, so it should be considered carefully.

Applications involving powers of 2

Since bit operations target binary representations, many applications involving integral powers of 2 follow naturally.

Multiplying (dividing) a number by a nonnegative integral power of 2:

C++

int mulPowerOfTwo(int n, int m) {  // Compute n*(2^m)
  return n << m;
}

int divPowerOfTwo(int n, int m) {  // Compute n/(2^m)
  return n >> m;
}

Python

def mulPowerOfTwo(n, m):  # Compute n*(2^m)
    return n << m

def divPowerOfTwo(n, m):  # Compute n/(2^m)
    return n >> m

Absolute value

On some machines, this is more efficient than n > 0 ? n : -n.

C++

int Abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
  /* n>>31 gives the sign of n: 0 when n is positive and -1 when n is negative
    For positive n, n^0=n and the number is unchanged; for negative n, n^(-1)
    computes the complements of n and -1, then applies XOR;
    the result changes the sign of n and is one less than its absolute value; subtracting -1 gives the absolute value */
}

Python

def Abs(n):
    return (n ^ (n >> 31)) - (n >> 31)
    """
    n >> 31 obtains the sign of n: it is 0 when n is positive and -1 when n is negative
    If n is positive, n ^ 0 = n and the value is unchanged; if n is negative, compute n ^ (-1)
    Compute the two's-complement representations of n and -1, then XOR them.
    This flips the sign and yields |n| - 1; subtracting -1 then gives the absolute value
    """

Maximum/minimum of two numbers

On some machines, this is more efficient than a > b ? a : b.

C++

// If a >= b, (a - b) >> 31 is 0; otherwise it is -1
int max(int a, int b) { return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31)); }

int min(int a, int b) { return (a & ((a - b) >> 31)) | (b & (~(a - b) >> 31)); }

Python

# If a >= b, (a - b) >> 31 is 0; otherwise, it is -1
def max(a, b):
    return b & ((a - b) >> 31) | a & (~(a - b) >> 31)

def min(a, b):
    return a & ((a - b) >> 31) | b & (~(a - b) >> 31)

Determining whether two nonzero numbers have the same sign

C++

bool isSameSign(int x, int y) {  // The case involving 0 is exceptional
  return (x ^ y) >= 0;
}

Python

# The case involving 0 is an exception
def isSameSign(x, y):
    return (x ^ y) >= 0

Swapping two numbers

void swap(int& a, int& b) { a ^= b ^= a ^= b; }

Manipulating the binary bits of a number

Get a particular bit of a number's binary representation:

C++

// Get bit b of a, with the least significant bit numbered 0
int getBit(int a, int b) { return (a >> b) & 1; }

Python

# Get bit b of a, with the least significant bit numbered 0
def getBit(a, b):
    return (a >> b) & 1

Set a particular bit of a number's binary representation to $0$:

C++

// Set bit b to 0, with the least significant bit numbered 0
int unsetBit(int a, int b) { return a & ~(1 << b); }

Python

# Set bit b to 0, with the least significant bit numbered 0
def unsetBit(a, b):
    return a & ~(1 << b)

Set a particular bit of a number's binary representation to $1$:

C++

// Set bit b to 1, with the least significant bit numbered 0
int setBit(int a, int b) { return a | (1 << b); }

Python

# Set bit b to 1, with the least significant bit numbered 0
def setBit(a, b):
    return a | (1 << b)

Invert a particular bit of a number's binary representation:

C++

// Invert bit b of a, with the least significant bit numbered 0
int flapBit(int a, int b) { return a ^ (1 << b); }

Python

# Invert bit b of a, with the least significant bit numbered 0
def flapBit(a, b):
    return a ^ (1 << b)

These operations are equivalent to treating a $32$-bit integer variable as a Boolean array of length $32$.

Hamming weight

The Hamming weight is the number of symbols in a string that differ from the zero symbol (defined in the character set being used). For a binary number, its Hamming weight is the number of $1$s (that is, popcount).

The Hamming weight of a number can be computed by looping: repeatedly remove the last bit of the number in binary (that is, right-shift by $1$), maintain an answer variable, and update the answer according to whether the least significant bit is $1$ during the division.

The code is as follows:

// Compute the Hamming weight of x
int popcount(int x) {
  int cnt = 0;
  while (x) {
    cnt += x & 1;
    x >>= 1;
  }
  return cnt;
}

The Hamming weight of a number can also be computed using the lowbit operation: repeatedly subtract its lowbit¹ until the number becomes $0$.

The code is as follows:

// Compute the Hamming weight of x
int popcount(int x) {
  int cnt = 0;
  while (x) {
    cnt++;
    x -= x & -x;
  }
  return cnt;
}

Constructing a permutation with increasing Hamming weights

In state-compression DP, enumerating in increasing order of popcount can sometimes avoid enumerating states repeatedly. This is one important use of constructing a permutation with increasing Hamming weights.

Let us investigate how to construct such a permutation in $O(n)$ time.

We know that the smallest integer with Hamming weight $n$ is $2^n-1$. If we can construct, in constant time, a successor with the same Hamming weight as an integer, then by enumerating Hamming weights and repeatedly finding the next number starting from $2^n-1$, we can construct in $O(n)$ time the required permutation of $0\sim n$.

The successor of a number $x$ with the same Hamming weight can be found as follows, using $(10110)_2$ as an example:

• Move the rightmost $1$ of $(10110)_2$ one position to the left. If it cannot move, move the $1$ to its left, and so on, obtaining $(11010)_2$.

• In the resulting $(11010)_2$, move all the $1$s from the original position of the last moved $1$ through the least significant bit to the far right. The last moved $1$ was originally in the third position, so the last three bits $010$ should become $001$, giving $(11001)_2$.

This process can be optimized with bit operations:

  int t = x + (x & -x);
  x = t | ((((t & -t) / (x & -x)) >> 1) - 1);

• In the first step, we add lowbit to $x$. In binary, this is equivalent to replacing the rightmost consecutive block of $1$s in $x$ with a $1$ immediately to its left. For the binary number $(10110)_2$ mentioned above, adding its lowbit gives $(11000)_2$. This obtains the first half of the answer.
• We next fill the $1$s in the rest of the answer. The lowbit of $t$ is the position after moving the leftmost $1$ of the rightmost consecutive block of $1$s in $x$, while the lowbit of $x$ is the position of the rightmost $1$ of $x$ in that block. For $(10110)_2$, $t = (11000)_2$, $\operatorname{lowbit}(t) = (01000)_2$, and $\operatorname{lowbit}(x)=(00010)_2$.
• The division operation that follows is the hardest part of this bit operation to understand, but also the most crucial. Let the highest-position $1$ in the rightmost consecutive block of $1$s of the original number be at position $r$ (positions start at $0$), and the lowest-position $1$ at position $l$. Then the lowbit of $t$ equals 1 << (r+1), and the lowbit of $x$ equals 1 << l; (((t&-t)/(x&-x))>>1) gives (1<<(r+1))/(1<<l)/2 = (1<<r)/(1<<l) = 1<<(r-l), which in binary is a $1$ followed by $r-l$ zeros. The number of zeros is exactly the number of consecutive $1$s minus $1$. In our example, $\frac{\operatorname{lowbit(t)/2}}{\operatorname{lowbit(x)}} = \frac{(00100)_2}{(00010)_2} = (00010)_2$. Subtracting $1$ yields the low bits to fill; ORing this with the original number gives the answer.

Therefore, the complete code for enumerating $0\sim n$ in increasing Hamming-weight order is:

  for (int i = 0; (1 << i) - 1 <= n; i++) {
    for (int x = (1 << i) - 1, t; x <= n; t = x + (x & -x),
             x = x ? (t | ((((t & -t) / (x & -x)) >> 1) - 1)) : (n + 1)) {
      // Write the operation to be completed
    }
  }

The special case $0$ must be handled, because $0$ has no successor with the same Hamming weight.

Related classes and functions in C++

GCC built-in functions

GCC also has several built-in functions for bit operations:

• int __builtin_ffs(int x): returns the position of the last $1$ in the binary representation of $x$, with positions numbered from $1$ (the least significant bit is numbered $1$). It returns $0$ when $x$ is $0$.
• int __builtin_clz(unsigned int x): returns the number of leading $0$s in the binary representation of $x$. The result is undefined when $x$ is $0$.
• int __builtin_ctz(unsigned int x): returns the number of consecutive trailing $0$s in the binary representation of $x$. The result is undefined when $x$ is $0$.
• int __builtin_clrsb(int x): when the sign bit of $x$ is $0$, returns the number of leading $0$s in the binary representation of $x$ minus one; otherwise, it returns the number of leading $1$s of $x$ minus one.
• int __builtin_popcount(unsigned int x): returns the number of $1$s in the binary representation of $x$.
• int __builtin_parity(unsigned int x): determines whether the number of $1$s in the binary representation of $x$ is odd or even.

Each of these functions can have l or ll appended to its name (for example, __builtin_popcountll) to change the parameter type to (unsigned)long or (unsigned)long long; the return type remains int. For example, we sometimes want to find the base-2 logarithm of a number. Ignoring the special case of 0, this is equivalent to the number of bits in its binary representation minus -1. The number of bits in the binary representation of an N-bit integer n can be expressed as N - __builtin_clz(n), so N - 1 - __builtin_clz(n) gives the base-2 logarithm of n.

Since these are built-in functions, they have been highly optimized by the compiler and run very quickly (some need only a single instruction).

More bits

If the bit sequence to be operated on is very long, use std::bitset.

Recommended problems

• Luogu P1225 Reversi

References and notes

1. Bit Twiddling Hacks
2. Bit Operation Builtins (Using the GNU Compiler Collection (GCC))
3. Bitwise operation