🐟 Blog

Bit manipulation cheatsheet

March 31, 2021

Get a bit

00010111&0000000100000001\begin{array}{ccc} &0001&0111 \\ \And & 0000 & 000\textcolor{#EC407A}{1} \\ \hline & 0000 & 0001 \end{array}

Get last bit

n & 1

Check if n is even

n & 1 == 0

Get bit at position k

(n >> k) & 1

Set / clear a bit at position k

Set a bit

00010111∣0000100000011111\begin{array}{ccc} & 0001 & 0111 \\ \mathbin{|} & 0000 & \textcolor{#EC407A}{1}000 \\ \hline & 0001 & 1111 \end{array}
n |= 1 << k

Clear a bit

00010111&1111101100010011\begin{array}{ccc} & 0001 & 0111 \\ \And & 1111 & 1\textcolor{#EC407A}{0}11 \\ \hline & 0001 & 0011 \end{array}
n &= ~(1 << k)

Toggle a bit

^01001110\begin{array}{ccc} \verb!^! & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & \textcolor{#ec407a}{0} \end{array}
πŸ’‘

^ is similar to | except that 1xor1=01 xor 1 = 0.

n ^= 1 << n

Masking

Write C expressions, in terms of variable x, for the following values.

The least significant byte of x, with all other bits set to 00.

x & 0xff

The least significant byte set to all ones, and all other bytes of x left unchanged.

x | 0xff

β€” CS-APP practice problem 2.12

n & (n - 1) trick

πŸ›ŽοΈ

n & n - 1 has the effect of flipping the least significant 11 bit of n.

Check out this detailed explanation.

You can use this trick to solve following LeetCode questions.

LeetCode
public int hammingWeight(int n) {
  int ret = 0;
  for (; n != 0; n = n & (n - 1)) ret++οΌ›
  return ret;
}
LeetCode

Notice in the decimal system, we write 10n10^n as 11 followed by nn zeros.

By the same token, the binary representation of 2n2^n is 11 followed by nn zeros.

// Check if the number would turn to 0
// after flipping the least significant 1 bit.
public boolean isPowerOfTwo(int n) {
  if (n == 0) return false;
  long N = (long) n;
  return (N & (N - 1)) == 0;
}
LeetCode

To check if a number is a power of 44, we first check if it’s power of 22 by applying the n&(nβˆ’1)n \And (n - 1) trick. A power of 22 number has only one 11 bit. If it’s power of 44, this 11 bit must be followed by an even number of 00 bits. In other words, the 11 bit must appear at even position of the binary representation. We can use a bit mask to check if the 1 bit is at odd position. If so, it’s not power of 44.

public boolean isPowerOfFour(int n) {
  if (n == 0) return false;
  long N = (long) n;
  return (N & (N - 1)) == 0
   && (N & 0xaaaaaaaa) == 0;
}

Note 0xa is equivalent to 0b1010.

Reference


Β© Attribution Required | θ½¬θ½½θ―·ζ³¨ζ˜ŽεŽŸδ½œθ€…δΈŽζœ¬η«™ι“ΎζŽ₯
Β© 2022 yujinyan.me