Bitwise Operations

Bitwise operations are operations performed on integers based on their binary representation. Since computers store data internally in binary, bitwise operations are quite fast.

There are six basic bitwise operations: bitwise AND, bitwise OR, bitwise XOR, bitwise NOT, left shift, and right shift.

For convenience, "bitwise" is omitted in the following discussion.

AND, OR, XOR

These three are operations between two numbers, so they are explained together here.

They all treat two integers as binary numbers and perform operations on each bit of their binary representations.

Operation	Operator	Mathematical Symbol	Explanation
AND	`&`	\(\&\), \(\operatorname{and}\)	Only when both corresponding bits are \(1\) is the result \(1\)
OR	`\|`	\(\mid\), \(\operatorname{or}\)	When at least one of the two corresponding bits is \(1\), the result is \(1\)
XOR	`^`	\(\oplus\), \(\operatorname{xor}\)	Only when the two corresponding bits differ is the result \(1\)

Note the distinction between logical AND (mathematical symbol \(\wedge\)) and bitwise AND, and between logical OR (\(\vee\)) and bitwise OR. Many online resources use non-standard symbols; rely on context.

The inverse operation of XOR is itself, meaning that XOR-ing the same number twice leaves the result unchanged, i.e., \(a \oplus b \oplus b = a\).

Example:

\[ \begin{aligned} 5 &=(101)_2\\ 6 &=(110)_2\\ 5\operatorname\&6 &=(100)_2 =\ 4\\ 5\operatorname|6 &=(111)_2 =\ 7\\ 5\oplus6 &=(011)_2 =\ 3\\ \end{aligned} \]

NOT

NOT is a unary bitwise operation performed on a single number \(num\).

There is no default mathematical symbol for NOT; its operator is ~. It flips all bits in the two's complement binary representation of \(num\) (0 becomes 1, 1 becomes 0). For signed integers, the sign bit is also flipped.

Two's complement: In binary representation, the two's complement of a positive number or zero is itself. For a negative number, its two's complement is obtained by taking the bitwise NOT of its corresponding positive number and adding one.

Example (signed integer):

\[ \begin{aligned} 5&=(00000101)_2\\ \text{~}5&=(11111010)_2=-6\\ -5\text{ two's complement}&=(11111011)_2\\ \text{~}(-5)&=(00000100)_2=4 \end{aligned} \]

Left Shift and Right Shift

num << i shifts the binary representation of \(num\) left by \(i\) bits.

num >> i shifts the binary representation of \(num\) right by \(i\) bits.

Example:

\[ \begin{aligned} 11&=(00001011)_2\\ 11<<3&=(01011000)_2=88\\ 11>>2&=(00000010)_2=2 \end{aligned} \]

In shift operations, the behavior is undefined if:

The right operand (shift amount) is negative;
The right operand is greater than or equal to the bit width of the left operand;

For example, for an int variable a, both a<<-1 and a<<32 are undefined.

For left shift, ensure the shifted result fits within the type of the original number; otherwise, the behavior is undefined.¹ Left shifting a negative number is also undefined.²

For right shift, excess bits on the right are discarded. The left side is more complex: for unsigned numbers, zeros are padded on the left; for signed numbers, the highest bit (the sign bit, 0 for non-negative, 1 for negative) is used for padding.³

Compound Assignment Bitwise Operators

Similar to +=, -=, etc., bitwise operations also have compound assignment operators: &=, |=, ^=, <<=, >>=. (NOT is unary, so it doesn't have one.)

About Precedence

Bitwise operators have lower precedence than arithmetic operators (except NOT), while bitwise AND, OR, and XOR have lower precedence than comparison operators (see C++ Operator Precedence Table). Therefore, be cautious and add parentheses when necessary.

Applications of Bitwise Operations

Bitwise operations generally serve three purposes:

Efficiently perform certain operations, replacing less efficient methods.
Represent sets (commonly used in State Compression DP).
The problem itself requires bitwise operations.

Note that replacing other operations with bitwise operations (the first purpose) often does not bring significant optimization and may complicate the code. Use with discretion. (However, operations like "multiply by a non-negative integer power of 2" and "divide by a non-negative integer power of 2" are best done with bitwise operations, as they optimize complexity.)

Since bitwise operations work on binary bits, many applications related to integer powers of 2 can be derived.

Multiply or divide a number by a non-negative integer power of 2:

C++Python

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;
}

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

Warning

The usual division rounds toward zero, while right shift here rounds down (note the difference). For non-negative numbers, the two are equivalent. For negative numbers, they differ: e.g., -1 / 2 equals \(0\), while -1 >> 1 equals \(-1\).

Absolute Value

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

C++Python

int Abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
  /* n>>31 gets the sign of n. If n is positive, n>>31 equals 0; if n is negative, n>>31 equals -1.
     If n is positive, n^0=n, unchanged. If n is negative, n^(-1) is computed.
     Need to compute the two's complement of n and -1, then XOR.
     The result changes the sign of n and becomes |n|-1, then subtracting -1 gives the absolute value. */
}

def Abs(n):
    return (n ^ (n >> 31)) - (n >> 31)
    """
    n>>31 gets the sign of n. If n is positive, n>>31 equals 0; if n is negative, n>>31 equals -1.
    If n is positive, n^0=n, unchanged. If n is negative, n^(-1) is computed.
    Need to compute the two's complement of n and -1, then XOR.
    The result changes the sign of n and becomes |n|-1, then subtracting -1 gives the absolute value.
    """

Maximum/Minimum of Two Numbers

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

C++Python

// If a >= b, (a - b) >> 31 is 0, otherwise -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)); }

# If a >= b, (a - b) >> 31 is 0, otherwise -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)

Check if Two Non-Zero Numbers Have the Same Sign

C++Python

bool isSameSign(int x, int y) {  // Except when there is 0
  return (x ^ y) >= 0;
}

# Except when there is 0
def isSameSign(x, y):
    return (x ^ y) >= 0

Swap Two Numbers

Limitations of This Method

This method can only swap two integers and has limited applicability.

For general swapping, it is recommended to call the std::swap function from the algorithm library.

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

Manipulating Bits of a Number

Get a specific bit of a number:

C++Python

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

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

Set a specific bit of a number to \(0\):

C++Python

// Set the b-th bit of a to 0, with the lowest bit numbered 0
int unsetBit(int a, int b) { return a & ~(1 << b); }

# Set the b-th bit of a to 0, with the lowest bit numbered 0
def unsetBit(a, b):
    return a & ~(1 << b)

Set a specific bit of a number to \(1\):

C++Python

// Set the b-th bit of a to 1, with the lowest bit numbered 0
int setBit(int a, int b) { return a | (1 << b); }

# Set the b-th bit of a to 1, with the lowest bit numbered 0
def setBit(a, b):
    return a | (1 << b)

Flip a specific bit of a number:

C++Python

// Flip the b-th bit of a, with the lowest bit numbered 0
int flapBit(int a, int b) { return a ^ (1 << b); }

# Flip the b-th bit of a, with the lowest bit numbered 0
def flapBit(a, b):
    return a ^ (1 << b)

These operations effectively treat a 32-bit integer as a boolean array of length 32.

Hamming Weight

The Hamming weight of a string is the number of symbols that are different from the zero-symbol (defined on the character set used). For a binary number, its Hamming weight equals the number of \(1\)s (i.e., popcount).

To compute the Hamming weight of a number, we can loop: repeatedly remove the last bit of the number (i.e., right shift by 1), maintain an answer variable, and update the answer based on whether the lowest bit is \(1\).

Code:

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

Another method uses lowbit operations: repeatedly subtract the lowbit⁴ of the number until it becomes \(0\).

Code:

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

Constructing Permutations with Increasing Hamming Weight

In State Compression DP, enumerating states in increasing order of popcount can sometimes avoid redundant enumeration. This is a major use of constructing permutations with increasing Hamming weight.

Let's explore how to construct such permutations in \(O(n)\) time.

We know that the smallest integer with Hamming weight \(n\) is \(2^n-1\). If we can find the successor with the same Hamming weight in constant time, we can start from \(2^n-1\) and repeatedly find the next number, constructing the required permutation for \(0\sim n\) in \(O(n)\) time.

To find the successor of a number \(x\) with the same Hamming weight, consider \((10110)_2\) as an example:

Move the rightmost \(1\) to the left. If not possible, move the \(1\) to its left, and so on, obtaining \((11010)_2\).
Move all \(1\)s from the original position of the last moved \(1\) down to the lowest bits to the far right. Here, the last moved \(1\) was originally at the third bit, so the last three bits \(010\) become \(001\), yielding \((11001)_2\).

This process can be optimized with bitwise 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 replaces the rightmost consecutive block of \(1\)s with a single \(1\) to its left. For example, \((10110)_2\) becomes \((11000)_2\) after adding its lowbit. This gives the first part of our answer.
Next, we need to fill in the trailing \(1\)s. The lowbit of \(t\) is the position of the leftmost \(1\) in the original consecutive block after moving. The lowbit of \(x\) is the position of the rightmost \(1\) in that block. For \((10110)_2\), \(t = (11000)_2\), \(\operatorname{lowbit}(t) = (01000)_2\), \(\operatorname{lowbit}(x)=(00010)_2\).
The division operation is the trickiest but most crucial part. Let the highest \(1\) in the original consecutive block be at position \(r\) (0-indexed), and the lowest \(1\) at position \(l\). Then lowbit(t) equals 1 << (r+1), and lowbit(x) equals 1 << l. (((t&-t)/(x&-x))>>1) yields (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 equals the length of the consecutive \(1\)s minus \(1\). For our example, \(\frac{\operatorname{lowbit(t)/2}}{\operatorname{lowbit(x)}} = \frac{(00100)_2}{(00010)_2} = (00010)_2\). Subtracting \(1\) gives the low bits to fill, and OR-ing with the original number yields the answer.

Thus, the complete code to enumerate permutations of \(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)) {
        // Perform desired operations
    }
}

Note the special handling for \(0\), as \(0\) has no successor with the same Hamming weight.

Built-in Functions

GCC provides some built-in functions for bitwise operations:

int __builtin_ffs(int x) : Returns the position of the last \(1\) in the binary representation of \(x\), with positions numbered starting from \(1\) (lowest bit is \(1\)). Returns \(0\) if \(x\) is \(0\).
int __builtin_clz(unsigned int x) : Returns the number of leading zeros in the binary representation of \(x\). Undefined when \(x\) is \(0\).
int __builtin_ctz(unsigned int x) : Returns the number of trailing zeros in the binary representation of \(x\). Undefined when \(x\) is \(0\).
int __builtin_clrsb(int x) : If the sign bit of \(x\) is \(0\), returns the number of leading zeros minus one; otherwise, returns the number of leading ones 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) : Returns the parity (odd/even) of the number of \(1\)s in the binary representation of \(x\).

These functions can have l or ll appended to the function name (e.g., __builtin_popcountll) to change the parameter type to ( unsigned ) long or ( unsigned ) long long (the return type remains int).

For example, to compute the base-2 logarithm of a number (ignoring the special case of \(0\)), it's equivalent to the number of bits minus \(1\). The number of bits in binary representation of n can be expressed as 32-__builtin_clz(n), so 31-__builtin_clz(n) gives the base-2 logarithm of n.

Since these are built-in functions, they are highly optimized by the compiler and run very fast (some even require only one instruction).

More Bits

If the set to operate on is very large, consider using bitset.

References and Notes

Bit Twiddling Hacks: https://graphics.stanford.edu/~seander/bithacks.html
Other Builtins of GCC: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

Applies to standards before C++14. In C++14 and C++17, if the original value is a signed type and the shifted result fits in the unsigned version of the type, the result is converted to the corresponding signed value; otherwise, the behavior is undefined. In C++20, it is specified that for both signed and unsigned numbers, left shift directly discards bits that exceed the result type. ↩
Applies to standards before C++20. ↩
This type of right shift is called arithmetic right shift. Before C++20, the implementation of right shift for signed numbers was not specified; most platforms used arithmetic right shift. C++20 specifies that right shift for signed numbers is arithmetic right shift. ↩
The lowest \(1\) in the binary representation along with all trailing zeros, e.g., the lowbit of \((1010)_2\) is \((0010)_2\). See Fenwick Tree. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

Bitwise Operations

AND, OR, XOR

NOT

Left Shift and Right Shift

Compound Assignment Bitwise Operators

About Precedence

Applications of Bitwise Operations

Applications Related to Powers of 2

Absolute Value

Maximum/Minimum of Two Numbers

Check if Two Non-Zero Numbers Have the Same Sign

Swap Two Numbers

Manipulating Bits of a Number

Hamming Weight

Constructing Permutations with Increasing Hamming Weight

Built-in Functions

More Bits

Recommended Problems

References and Notes