🧩 Patterns

Bit Tricks

n & 1, n & (n-1), XOR patterns — O(1) operations that replace loops

Bit operations appear in a specific class of interview problems. You don't need many — just these patterns cover most cases.

Language:
Python
Loading...

All languages — Essential bit operations

JavaScript
const n = 12;  // binary: 1100

// Is odd?
n & 1             // 0 = even, 1 = odd

// Is power of 2?
(n & (n - 1)) === 0   // false (12 is not)
(16 & 15) === 0        // true

// Clear lowest set bit:
n & (n - 1)       // 8

// Get lowest set bit:
n & (-n)          // 4

// XOR: find the single non-duplicate
const nums = [2, 3, 2, 4, 4];
const unique = nums.reduce((acc, x) => acc ^ x, 0);
console.log(unique);  // 3

// Count set bits:
n.toString(2).split('0').join('').length  // 2
// or: use a loop with n & 1, then n >>= 1
TypeScript
const n: number = 12;

const isOdd = (x: number) => (x & 1) === 1;
const isPow2 = (x: number) => x > 0 && (x & (x - 1)) === 0;

const nums: number[] = [2, 3, 2, 4, 4];
const unique: number = nums.reduce((acc, x) => acc ^ x, 0);
console.log(unique);  // 3
Java
int n = 12;

// Is odd?
(n & 1) == 1       // false

// Is power of 2?
(n & (n-1)) == 0   // false
Integer.bitCount(n) == 1  // also checks power of 2

// Clear lowest set bit:
n & (n-1)          // 8

// XOR: find single non-duplicate
int[] nums = {2, 3, 2, 4, 4};
int unique = 0;
for (int x : nums) unique ^= x;
System.out.println(unique);  // 3

// Count set bits:
Integer.bitCount(12);   // 2
Go
import "math/bits"

n := 12

// Is odd?
n & 1 == 1        // false

// Is power of 2?
n & (n-1) == 0    // false
bits.OnesCount(uint(n)) == 1  // also works

// Clear lowest set bit:
n & (n - 1)       // 8

// XOR: find single non-duplicate
nums := []int{2, 3, 2, 4, 4}
unique := 0
for _, x := range nums { unique ^= x }
fmt.Println(unique)  // 3

// Count set bits:
bits.OnesCount(uint(n))   // 2
C++
#include <bit>  // C++20

int n = 12;

// Is odd?
n & 1             // 0 = even

// Is power of 2?
(n & (n-1)) == 0  // false
std::has_single_bit((unsigned)n)  // C++20

// Clear lowest set bit:
n & (n-1)         // 8

// XOR: find single non-duplicate
vector<int> nums = {2, 3, 2, 4, 4};
int unique = 0;
for (int x : nums) unique ^= x;
cout << unique << endl;  // 3

// Count set bits:
__builtin_popcount(n)           // 2 (GCC)
std::popcount((unsigned)n)      // 2 (C++20)