Bit manipulation treats an integer as a row of 0/1 switches. A handful of operators (& | ^ ~ << >>) and a dozen tricks turn O(n) counting problems into O(1) formulas, cancel paired elements with XOR, and enumerate every subset of a set with a counter.

Binary representation and two's complement

An n-bit integer has n positions; bit 0 is the least significant bit (LSB, rightmost, worth 1) and bit n-1 the most significant bit (MSB, leftmost). Unsigned numbers use all bits for magnitude; signed numbers use two's complement, where the MSB acts as the sign and the representable range is -2^(n-1) … 2^(n-1) - 1.

Write the positive number
3 in 4 bits is 0011.
Invert every bit
0011 → 1100 (this is the one's complement).
Add 1
1100 + 1 → 1101. That is -3 in 4-bit two's complement.

two's complement of x in n bits = 2^n − x (4 bits: 16 − 3 = 13 = 1101)

Every 4-bit pattern is used exactly once; there is only one zero

4-bit two's complement (range -8 … 7)

 bits   value         bits   value
 0000     0           1000    -8   ← MSB set ⇒ negative
 0001     1           1001    -7
 0010     2           1010    -6
 0011     3           1011    -5
 0100     4           1100    -4
 0101     5           1101    -3
 0110     6           1110    -2
 0111     7           1111    -1

Why two's complement rather than a separate sign bit? Three reasons that make hardware simpler:

One zero. A sign-magnitude scheme has +0 and -0; two's complement has a single 0000.
Addition just works. The same adder handles positive and negative operands: 3 + (-3) = 0011 + 1101 = 1 0000, and dropping the carry gives 0000. Subtraction is addition of the complement, which is where the name 0 − x comes from.
The leading bit is the sign. MSB 1 ⇒ negative, so a sign test is a single bit check.

Python

def bits(x, n):
    # the low n bits of x, most significant first ((x >> i) & 1 picks bit i)
    return "".join("1" if (x >> i) & 1 else "0" for i in range(n - 1, -1, -1))

for x in (3, 7, -1, -3, -8):
    print(x, "in 4 bits:", bits(x, 4))
print("2^4 - 3 =", (1 << 4) - 3, "->", bits((1 << 4) - 3, 4))

C++

#include <iostream>
#include <string>
using namespace std;

string bits(int x, int n) {
    string s;
    for (int i = n - 1; i >= 0; i--)        // (x >> i) & 1 picks bit i
        s += ((x >> i) & 1) ? '1' : '0';
    return s;
}

int main() {
    for (int x : {3, 7, -1, -3, -8})
        cout << x << " in 4 bits: " << bits(x, 4) << "\n";
    cout << "2^4 - 3 = " << ((1 << 4) - 3) << " -> " << bits((1 << 4) - 3, 4) << "\n";
}

Java

public class Main {
    static String bits(int x, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = n - 1; i >= 0; i--)    // (x >> i) & 1 picks bit i
            sb.append((x >> i) & 1);
        return sb.toString();
    }

    public static void main(String[] args) {
        for (int x : new int[]{3, 7, -1, -3, -8})
            System.out.println(x + " in 4 bits: " + bits(x, 4));
        System.out.println("2^4 - 3 = " + ((1 << 4) - 3) + " -> " + bits((1 << 4) - 3, 4));
    }
}

JavaScript

function bits(x, n) {
    let s = "";
    for (let i = n - 1; i >= 0; i--)        // (x >> i) & 1 picks bit i
        s += (x >> i) & 1;
    return s;
}

for (const x of [3, 7, -1, -3, -8])
    console.log(x, "in 4 bits:", bits(x, 4));
console.log("2^4 - 3 =", (1 << 4) - 3, "->", bits((1 << 4) - 3, 4));

Output

3 in 4 bits: 0011
7 in 4 bits: 0111
-1 in 4 bits: 1111
-3 in 4 bits: 1101
-8 in 4 bits: 1000
2^4 - 3 = 13 -> 1101

Bitwise operators

Operator	Name	Rule per bit	`12 (1100)` with `10 (1010)`
`a & b`	AND	1 only if both bits are 1	`1000` = 8
`a \| b`	OR	1 if either bit is 1	`1110` = 14
`a ^ b`	XOR	1 if the bits differ	`0110` = 6
`~a`	NOT	flips every bit; equals `-a - 1` in two's complement	`~12` = -13
`a << k`	left shift	shift left, zeros enter on the right; multiplies by `2^k`	`12 << 2` = 48
`a >> k`	right shift	shift right, drops the low bits; divides by `2^k` (floor)	`12 >> 2` = 3

Python

def bits(x, n):
    return "".join("1" if (x >> i) & 1 else "0" for i in range(n - 1, -1, -1))

def show(label, v):
    print(f"{label} = {v} -> {bits(v, 8)}")

a, b = 12, 10
show("a", a)
show("b", b)
show("a & b", a & b)
show("a | b", a | b)
show("a ^ b", a ^ b)
show("~a", ~a)            # -13: Python prints the signed value, low 8 bits are 11110011
show("a << 2", a << 2)
show("a >> 2", a >> 2)

C++

#include <iostream>
#include <string>
using namespace std;

string bits(int x, int n) {
    string s;
    for (int i = n - 1; i >= 0; i--) s += ((x >> i) & 1) ? '1' : '0';
    return s;
}

void show(const string& label, int v) {
    cout << label << " = " << v << " -> " << bits(v, 8) << "\n";
}

int main() {
    int a = 12, b = 10;
    show("a", a);
    show("b", b);
    show("a & b", a & b);
    show("a | b", a | b);
    show("a ^ b", a ^ b);
    show("~a", ~a);           // -13 in a 32-bit int: low 8 bits are 11110011
    show("a << 2", a << 2);
    show("a >> 2", a >> 2);
}

Java

public class Main {
    static String bits(int x, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = n - 1; i >= 0; i--) sb.append((x >> i) & 1);
        return sb.toString();
    }

    static void show(String label, int v) {
        System.out.println(label + " = " + v + " -> " + bits(v, 8));
    }

    public static void main(String[] args) {
        int a = 12, b = 10;
        show("a", a);
        show("b", b);
        show("a & b", a & b);
        show("a | b", a | b);
        show("a ^ b", a ^ b);
        show("~a", ~a);       // -13 in a 32-bit int: low 8 bits are 11110011
        show("a << 2", a << 2);
        show("a >> 2", a >> 2);
    }
}

JavaScript

function bits(x, n) {
    let s = "";
    for (let i = n - 1; i >= 0; i--) s += (x >> i) & 1;
    return s;
}

function show(label, v) {
    console.log(`${label} = ${v} -> ${bits(v, 8)}`);
}

const a = 12, b = 10;
show("a", a);
show("b", b);
show("a & b", a & b);
show("a | b", a | b);
show("a ^ b", a ^ b);
show("~a", ~a);               // JS converts to a 32-bit int first: -13
show("a << 2", a << 2);
show("a >> 2", a >> 2);

Output

a = 12 -> 00001100
b = 10 -> 00001010
a & b = 8 -> 00001000
a | b = 14 -> 00001110
a ^ b = 6 -> 00000110
~a = -13 -> 11110011
a << 2 = 48 -> 00110000
a >> 2 = 3 -> 00000011

Language differences you must know

	Python	C++ / Java	JavaScript
Width of an `int`	unbounded — `1 << 100` is fine, `~x` is always `-x-1`	32-bit `int`, 64-bit `long`/`long long`; overflow wraps (Java) or is undefined for signed (C++)	numbers are doubles, but every bitwise operator converts to a 32-bit signed int first — `1 << 31` is `-2147483648`
`>>` on negatives	arithmetic (floor division by `2^k`)	arithmetic; C++ guarantees it since C++20	arithmetic
Logical (zero-fill) shift	not needed — mask first: `(x & 0xFFFFFFFF) >> k`	Java: `x >>> k`. C++: cast to `unsigned` first	`x >>> k`
Shift by ≥ width	fine (just a bigger number)	undefined in C++, taken mod 32/64 in Java	taken mod 32
Popcount built-in	`n.bit_count()` (3.10+) or `bin(n).count('1')`	`std::popcount` (`<bit>`, unsigned) / `__builtin_popcount`; `Integer.bitCount(n)`	none — `n.toString(2).split('1').length - 1`

Python

x = -16
print("-16 >> 2 =", x >> 2)                       # arithmetic: sign bit copied in
print("-16 >>> 2 =", (x & 0xFFFFFFFF) >> 2)       # emulate a 32-bit logical shift
print("1 << 10 =", 1 << 10)

C++

#include <iostream>
using namespace std;

int main() {
    int x = -16;
    cout << "-16 >> 2 = " << (x >> 2) << "\n";                        // arithmetic shift
    cout << "-16 >>> 2 = " << (static_cast<unsigned>(x) >> 2) << "\n"; // logical: shift as unsigned
    cout << "1 << 10 = " << (1 << 10) << "\n";
}

Java

public class Main {
    public static void main(String[] args) {
        int x = -16;
        System.out.println("-16 >> 2 = " + (x >> 2));     // arithmetic shift
        System.out.println("-16 >>> 2 = " + (x >>> 2));   // logical shift fills with zeros
        System.out.println("1 << 10 = " + (1 << 10));
    }
}

JavaScript

const x = -16;
console.log("-16 >> 2 =", x >> 2);        // arithmetic shift
console.log("-16 >>> 2 =", x >>> 2);      // logical shift; result is an unsigned 32-bit value
console.log("1 << 10 =", 1 << 10);

Output

-16 >> 2 = -4
-16 >>> 2 = 1073741820
1 << 10 = 1024

The classic tricks

Expression	What it does	Why
`n & 1`	`1` if `n` is odd	the LSB is the only odd place value
`n << 1`, `n >> 1`	`n * 2`, `n / 2` (floor)	shifting moves every bit to the next place value
`1 << k`	`2^k`, a mask with only bit `k` set	`1` moved `k` places left
`n & (1 << k)`	non-zero iff bit `k` is set	AND keeps only that bit
`n \| (1 << k)`	set bit `k`	OR with the mask forces a `1`
`n & ~(1 << k)`	clear bit `k`	AND with every bit except `k` set
`n ^ (1 << k)`	toggle bit `k`	XOR with `1` flips, with `0` keeps
`n & (n - 1)`	clear the rightmost set bit	subtracting 1 flips that bit and the zeros after it
`n & -n` (= `n & ~(n - 1)`)	isolate the rightmost set bit	`-n` agrees with `n` only at that bit
`n & (n - 1) == 0`	`n` is a power of two (for `n > 0`)	a power of two has exactly one set bit
`x ^ x = 0`, `x ^ 0 = x`	XOR cancels pairs	the basis of the odd-occurrence problems below
`a ^= b; b ^= a; a ^= b`	swap without a temporary	`a ^ b ^ b = a`

Decimal to binary and back

Repeated division by 2 produces the bits from the right: the remainder is the next bit, the quotient is what is left. Reading a binary string left to right is the reverse: value = value * 2 + bit. Both loops are O(number of bits) = O(log n).

Python

def to_binary(n):
    if n == 0:
        return "0"
    s = ""
    while n > 0:
        s = str(n % 2) + s      # remainder = next bit from the right
        n //= 2
    return s

def to_decimal(b):
    v = 0
    for ch in b:
        v = v * 2 + (1 if ch == '1' else 0)   # shift what we have, add the new bit
    return v

print(37, "->", to_binary(37))
print("100101", "->", to_decimal("100101"))

C++

#include <iostream>
#include <string>
using namespace std;

string toBinary(int n) {
    if (n == 0) return "0";
    string s;
    while (n > 0) {
        s = char('0' + n % 2) + s;     // remainder = next bit from the right
        n /= 2;
    }
    return s;
}

int toDecimal(const string& b) {
    int v = 0;
    for (char ch : b) v = v * 2 + (ch == '1' ? 1 : 0);   // shift what we have, add the new bit
    return v;
}

int main() {
    cout << 37 << " -> " << toBinary(37) << "\n";
    cout << "100101" << " -> " << toDecimal("100101") << "\n";
}

Java

public class Main {
    static String toBinary(int n) {
        if (n == 0) return "0";
        StringBuilder s = new StringBuilder();
        while (n > 0) {
            s.insert(0, n % 2);        // remainder = next bit from the right
            n /= 2;
        }
        return s.toString();
    }

    static int toDecimal(String b) {
        int v = 0;
        for (char ch : b.toCharArray()) v = v * 2 + (ch == '1' ? 1 : 0);   // shift, add the new bit
        return v;
    }

    public static void main(String[] args) {
        System.out.println(37 + " -> " + toBinary(37));
        System.out.println("100101" + " -> " + toDecimal("100101"));
    }
}

JavaScript

function toBinary(n) {
    if (n === 0) return "0";
    let s = "";
    while (n > 0) {
        s = (n % 2) + s;              // remainder = next bit from the right
        n = Math.floor(n / 2);
    }
    return s;
}

function toDecimal(b) {
    let v = 0;
    for (const ch of b) v = v * 2 + (ch === '1' ? 1 : 0);   // shift what we have, add the new bit
    return v;
}

console.log(37, "->", toBinary(37));
console.log("100101", "->", toDecimal("100101"));

Output

37 -> 100101
100101 -> 37

Check whether the kth bit is set

Bits are counted from the right, so the kth bit (1-based) is the mask 1 << (k - 1); k must not exceed the width of n. Two equivalent ways:

Both methods look at the same bit

n = 5 = 0 1 0 1          k = 3 → mask 1 << 2 = 0 1 0 0
        k=4 3 2 1
n & mask = 0 1 0 0  ≠ 0  → bit 3 is set
n >> 2   = 0 0 0 1  & 1 = 1 → the same answer, read at position 0

Python

def is_kth_set_mask(n, k):
    return (n & (1 << (k - 1))) != 0     # way 1: move the mask to the bit

def is_kth_set_shift(n, k):
    return ((n >> (k - 1)) & 1) == 1     # way 2: move the bit to position 0

n = 5
print("n =", n, "->", format(n, "04b"))
for k in range(1, 5):
    print(f"k = {k}:", "Yes" if is_kth_set_mask(n, k) else "No",
          "Yes" if is_kth_set_shift(n, k) else "No")

C++

#include <iostream>
#include <bitset>
using namespace std;

bool isKthSetMask(int n, int k) {
    return (n & (1 << (k - 1))) != 0;    // way 1: move the mask to the bit
}

bool isKthSetShift(int n, int k) {
    return ((n >> (k - 1)) & 1) == 1;    // way 2: move the bit to position 0
}

int main() {
    int n = 5;
    cout << "n = " << n << " -> " << bitset<4>(n) << "\n";
    for (int k = 1; k <= 4; k++)
        cout << "k = " << k << ": " << (isKthSetMask(n, k) ? "Yes" : "No")
             << " " << (isKthSetShift(n, k) ? "Yes" : "No") << "\n";
}

Java

public class Main {
    static boolean isKthSetMask(int n, int k) {
        return (n & (1 << (k - 1))) != 0;    // way 1: move the mask to the bit
    }

    static boolean isKthSetShift(int n, int k) {
        return ((n >> (k - 1)) & 1) == 1;    // way 2: move the bit to position 0
    }

    public static void main(String[] args) {
        int n = 5;
        String b = String.format("%4s", Integer.toBinaryString(n)).replace(' ', '0');
        System.out.println("n = " + n + " -> " + b);
        for (int k = 1; k <= 4; k++)
            System.out.println("k = " + k + ": " + (isKthSetMask(n, k) ? "Yes" : "No")
                               + " " + (isKthSetShift(n, k) ? "Yes" : "No"));
    }
}

JavaScript

function isKthSetMask(n, k) {
    return (n & (1 << (k - 1))) !== 0;   // way 1: move the mask to the bit
}

function isKthSetShift(n, k) {
    return ((n >> (k - 1)) & 1) === 1;   // way 2: move the bit to position 0
}

const n = 5;
console.log("n =", n, "->", n.toString(2).padStart(4, "0"));
for (let k = 1; k <= 4; k++)
    console.log(`k = ${k}:`, isKthSetMask(n, k) ? "Yes" : "No", isKthSetShift(n, k) ? "Yes" : "No");

Output

n = 5 -> 0101
k = 1: Yes Yes
k = 2: No No
k = 3: Yes Yes
k = 4: No No

Time O(1) · Space O(1)

Count set bits

The number of 1 bits is also called the population count or Hamming weight. There are four standard ways, from obvious to fastest.

Naive: walk the bits from LSB to MSB — n % 2 (or n & 1) reads the lowest bit, n // 2 (or n >> 1) drops it. Runs once per bit, set or not.

Python

def count_bits(n):
    res = 0
    while n:
        res += n & 1          # 1 if the lowest bit is set
        n >>= 1               # drop it
    return res

for n in (9, 13, 255, 1023):
    print(n, "->", count_bits(n))

C++

#include <iostream>
using namespace std;

int countBits(int n) {
    int res = 0;
    while (n) {
        res += n & 1;         // 1 if the lowest bit is set
        n >>= 1;              // drop it
    }
    return res;
}

int main() {
    for (int n : {9, 13, 255, 1023}) cout << n << " -> " << countBits(n) << "\n";
}

Java

public class Main {
    static int countBits(int n) {
        int res = 0;
        while (n != 0) {
            res += n & 1;     // 1 if the lowest bit is set
            n >>>= 1;         // logical shift so a negative n also terminates
        }
        return res;
    }

    public static void main(String[] args) {
        for (int n : new int[]{9, 13, 255, 1023}) System.out.println(n + " -> " + countBits(n));
    }
}

JavaScript

function countBits(n) {
    let res = 0;
    while (n !== 0) {
        res += n & 1;         // 1 if the lowest bit is set
        n >>>= 1;             // logical shift so a negative n also terminates
    }
    return res;
}

for (const n of [9, 13, 255, 1023]) console.log(n, "->", countBits(n));

Output

9 -> 2
13 -> 3
255 -> 8
1023 -> 10

Time O(number of bits) = O(log n) · Space O(1)

Brian Kernighan's algorithm: n & (n - 1) clears the rightmost set bit, so the loop runs once per set bit instead of once per bit position. For a sparse number it is much faster.

Subtracting 1 flips the rightmost 1 and every 0 after it; AND-ing keeps everything to its left

n = 13:   1101
1101 & 1100 = 1100   (12)   rightmost 1 cleared → count 1
1100 & 1011 = 1000   ( 8)                       → count 2
1000 & 0111 = 0000   ( 0)                       → count 3, stop

Python

def count_bits(n):
    res = 0
    while n:
        n &= n - 1            # clears the rightmost set bit
        res += 1
    return res

for n in (9, 13, 255, 1023):
    print(n, "->", count_bits(n))

C++

#include <iostream>
using namespace std;

int countBits(int n) {
    int res = 0;
    while (n) {
        n &= n - 1;           // clears the rightmost set bit
        res++;
    }
    return res;
}

int main() {
    for (int n : {9, 13, 255, 1023}) cout << n << " -> " << countBits(n) << "\n";
}

Java

public class Main {
    static int countBits(int n) {
        int res = 0;
        while (n != 0) {
            n &= n - 1;       // clears the rightmost set bit
            res++;
        }
        return res;
    }

    public static void main(String[] args) {
        for (int n : new int[]{9, 13, 255, 1023}) System.out.println(n + " -> " + countBits(n));
    }
}

JavaScript

function countBits(n) {
    let res = 0;
    while (n !== 0) {
        n &= n - 1;           // clears the rightmost set bit
        res++;
    }
    return res;
}

for (const n of [9, 13, 255, 1023]) console.log(n, "->", countBits(n));

Output

9 -> 2
13 -> 3
255 -> 8
1023 -> 10

Time O(number of set bits) · Space O(1)

Lookup table: precompute the count for every byte value 0…255 once (O(1), it is a constant 256 entries), then a 32-bit number is just four table reads. Each entry is built from a smaller one: tbl[i] = (i & 1) + tbl[i >> 1].

Python

tbl = [0] * 256
for i in range(1, 256):
    tbl[i] = (i & 1) + tbl[i >> 1]      # lowest bit + count of the rest

def count_bits(n):                      # 32-bit n: four bytes
    return (tbl[n & 0xff] + tbl[(n >> 8) & 0xff]
            + tbl[(n >> 16) & 0xff] + tbl[(n >> 24) & 0xff])

for n in (9, 13, 255, 1023):
    print(n, "->", count_bits(n))

C++

#include <iostream>
using namespace std;

int tbl[256];

void initialize() {
    for (int i = 1; i < 256; i++) tbl[i] = (i & 1) + tbl[i >> 1];   // lowest bit + count of the rest
}

int countBits(unsigned n) {             // unsigned: >> never drags a sign bit in
    return tbl[n & 0xff] + tbl[(n >> 8) & 0xff] + tbl[(n >> 16) & 0xff] + tbl[(n >> 24) & 0xff];
}

int main() {
    initialize();
    for (int n : {9, 13, 255, 1023}) cout << n << " -> " << countBits(n) << "\n";
}

Java

public class Main {
    static int[] tbl = new int[256];

    static void initialize() {
        for (int i = 1; i < 256; i++) tbl[i] = (i & 1) + tbl[i >> 1];   // lowest bit + count of the rest
    }

    static int countBits(int n) {       // >>> so a negative n gives the right 32-bit answer
        return tbl[n & 0xff] + tbl[(n >>> 8) & 0xff] + tbl[(n >>> 16) & 0xff] + tbl[(n >>> 24) & 0xff];
    }

    public static void main(String[] args) {
        initialize();
        for (int n : new int[]{9, 13, 255, 1023}) System.out.println(n + " -> " + countBits(n));
    }
}

JavaScript

const tbl = new Array(256).fill(0);
for (let i = 1; i < 256; i++) tbl[i] = (i & 1) + tbl[i >> 1];   // lowest bit + count of the rest

function countBits(n) {                 // >>> so a negative n gives the right 32-bit answer
    return tbl[n & 0xff] + tbl[(n >>> 8) & 0xff] + tbl[(n >>> 16) & 0xff] + tbl[(n >>> 24) & 0xff];
}

for (const n of [9, 13, 255, 1023]) console.log(n, "->", countBits(n));

Output

9 -> 2
13 -> 3
255 -> 8
1023 -> 10

Time O(1) — four lookups · Space O(1) — a fixed 256-entry table

Built-ins: in production code use the library — it compiles to a single popcnt instruction where the CPU has one.

Python

for n in (9, 13, 255, 1023):
    print(n, "->", n.bit_count())        # Python 3.10+; older: bin(n).count("1")

C++

#include <iostream>
#include <bit>
using namespace std;

int main() {
    for (int n : {9, 13, 255, 1023})
        cout << n << " -> " << popcount(static_cast<unsigned>(n)) << "\n";   // C++20; or __builtin_popcount(n)
}

Java

public class Main {
    public static void main(String[] args) {
        for (int n : new int[]{9, 13, 255, 1023})
            System.out.println(n + " -> " + Integer.bitCount(n));          // Long.bitCount for long
    }
}

JavaScript

for (const n of [9, 13, 255, 1023])
    console.log(n, "->", n.toString(2).split("1").length - 1);   // no popcount in JS: count '1's in the binary string

Output

9 -> 2
13 -> 3
255 -> 8
1023 -> 10

Is n a power of 2?

Naive: keep halving while n is even; it is a power of two if you end at exactly 1. O(log n).

Python

def is_power_of_two(n):
    if n == 0:
        return False
    while n != 1:
        if n % 2 != 0:          # an odd number above 1 cannot be a power of two
            return False
        n //= 2
    return True

for n in (4, 0, 1, 6, 1024):
    print(n, "->", "Yes" if is_power_of_two(n) else "No")

Output

4 -> Yes
0 -> No
1 -> Yes
6 -> No
1024 -> Yes

Python

def is_power_of_two(n):
    return n != 0 and (n & (n - 1)) == 0     # exactly one set bit

for n in (4, 0, 1, 6, 1024):
    print(n, "->", "Yes" if is_power_of_two(n) else "No")

C++

#include <iostream>
using namespace std;

bool isPowerOfTwo(int n) {
    return n != 0 && (n & (n - 1)) == 0;      // exactly one set bit
}

int main() {
    for (int n : {4, 0, 1, 6, 1024})
        cout << n << " -> " << (isPowerOfTwo(n) ? "Yes" : "No") << "\n";
}

Java

public class Main {
    static boolean isPowerOfTwo(int n) {
        return n != 0 && (n & (n - 1)) == 0;  // exactly one set bit
    }

    public static void main(String[] args) {
        for (int n : new int[]{4, 0, 1, 6, 1024})
            System.out.println(n + " -> " + (isPowerOfTwo(n) ? "Yes" : "No"));
    }
}

JavaScript

function isPowerOfTwo(n) {
    return n !== 0 && (n & (n - 1)) === 0;    // exactly one set bit
}

for (const n of [4, 0, 1, 6, 1024])
    console.log(n, "->", isPowerOfTwo(n) ? "Yes" : "No");

Output

4 -> Yes
0 -> No
1 -> Yes
6 -> No
1024 -> Yes

Time O(1) · Space O(1)

Find the one odd-occurring element

Every element appears an even number of times except one. Naive: for each element count its occurrences with a second loop and return the first with an odd count — O(n²).

Python

def find_odd(arr):
    for x in arr:
        count = 0
        for y in arr:               # O(n) count for each of the n elements
            if x == y:
                count += 1
        if count % 2 == 1:
            return x
    return -1

print(find_odd([10, 30, 30, 10, 30, 30, 20]))
print(find_odd([4, 3, 4, 4, 4, 5, 5]))

Output

20
3

Pairs cancel to 0; 0 is the XOR identity

  10 ^ 30 ^ 30 ^ 10 ^ 30 ^ 30 ^ 20
= (10 ^ 10) ^ (30 ^ 30) ^ (30 ^ 30) ^ 20      reorder: XOR is commutative
=    0      ^    0      ^    0      ^ 20
= 20

Python

def find_odd(arr):
    res = 0
    for x in arr:
        res ^= x              # pairs cancel: x ^ x = 0
    return res

for arr in ([10, 30, 30, 10, 30, 30, 20], [4, 3, 4, 4, 4, 5, 5]):
    print(" ".join(map(str, arr)), "->", find_odd(arr))

C++

#include <iostream>
#include <vector>
using namespace std;

int findOdd(const vector<int>& arr) {
    int res = 0;
    for (int x : arr) res ^= x;      // pairs cancel: x ^ x = 0
    return res;
}

int main() {
    vector<vector<int>> tests = {{10, 30, 30, 10, 30, 30, 20}, {4, 3, 4, 4, 4, 5, 5}};
    for (const auto& arr : tests) {
        for (int x : arr) cout << x << " ";
        cout << "-> " << findOdd(arr) << "\n";
    }
}

Java

public class Main {
    static int findOdd(int[] arr) {
        int res = 0;
        for (int x : arr) res ^= x;  // pairs cancel: x ^ x = 0
        return res;
    }

    public static void main(String[] args) {
        int[][] tests = {{10, 30, 30, 10, 30, 30, 20}, {4, 3, 4, 4, 4, 5, 5}};
        for (int[] arr : tests) {
            StringBuilder sb = new StringBuilder();
            for (int x : arr) sb.append(x).append(' ');
            System.out.println(sb + "-> " + findOdd(arr));
        }
    }
}

JavaScript

function findOdd(arr) {
    let res = 0;
    for (const x of arr) res ^= x;   // pairs cancel: x ^ x = 0
    return res;
}

for (const arr of [[10, 30, 30, 10, 30, 30, 20], [4, 3, 4, 4, 4, 5, 5]])
    console.log(arr.join(" "), "->", findOdd(arr));

Output

10 30 30 10 30 30 20 -> 20
4 3 4 4 4 5 5 -> 3

Time O(n) · Space O(1)

Find the two odd-occurring elements

Now exactly two elements, x and y, occur an odd number of times. XOR-ing everything gives x ^ y, which is not enough on its own — we need to separate them.

The rightmost differing bit splits the two odd elements into different groups

arr = 3 4 3 4 5 4 4 6 7 7
XOR of all      = 5 ^ 6 = 101 ^ 110 = 011          (every pair cancels)
rightmost 1 bit = 011 & -011 = 001                 (5 and 6 differ in bit 0)

bit 0 set   : 3 3 5 7 7   → XOR = 5
bit 0 clear : 4 4 4 4 6   → XOR = 6

Python

def two_odd(arr):
    xors = 0
    for x in arr:
        xors ^= x                 # = x ^ y
    sn = xors & -xors             # rightmost set bit (same as xors & ~(xors - 1))
    res1 = res2 = 0
    for x in arr:
        if x & sn:
            res1 ^= x             # group with the bit set
        else:
            res2 ^= x             # group with the bit clear
    return min(res1, res2), max(res1, res2)

for arr in ([3, 4, 3, 4, 5, 4, 4, 6, 7, 7], [20, 15, 20, 16]):
    a, b = two_odd(arr)
    print(" ".join(map(str, arr)), "->", a, b)

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

pair<int, int> twoOdd(const vector<int>& arr) {
    int xors = 0;
    for (int x : arr) xors ^= x;        // = x ^ y
    int sn = xors & -xors;              // rightmost set bit (same as xors & ~(xors - 1))
    int res1 = 0, res2 = 0;
    for (int x : arr) {
        if (x & sn) res1 ^= x;          // group with the bit set
        else        res2 ^= x;          // group with the bit clear
    }
    return {min(res1, res2), max(res1, res2)};
}

int main() {
    vector<vector<int>> tests = {{3, 4, 3, 4, 5, 4, 4, 6, 7, 7}, {20, 15, 20, 16}};
    for (const auto& arr : tests) {
        for (int x : arr) cout << x << " ";
        auto [a, b] = twoOdd(arr);
        cout << "-> " << a << " " << b << "\n";
    }
}

Java

public class Main {
    static int[] twoOdd(int[] arr) {
        int xors = 0;
        for (int x : arr) xors ^= x;    // = x ^ y
        int sn = xors & -xors;          // rightmost set bit (same as xors & ~(xors - 1))
        int res1 = 0, res2 = 0;
        for (int x : arr) {
            if ((x & sn) != 0) res1 ^= x;   // group with the bit set
            else               res2 ^= x;   // group with the bit clear
        }
        return new int[]{Math.min(res1, res2), Math.max(res1, res2)};
    }

    public static void main(String[] args) {
        int[][] tests = {{3, 4, 3, 4, 5, 4, 4, 6, 7, 7}, {20, 15, 20, 16}};
        for (int[] arr : tests) {
            StringBuilder sb = new StringBuilder();
            for (int x : arr) sb.append(x).append(' ');
            int[] r = twoOdd(arr);
            System.out.println(sb + "-> " + r[0] + " " + r[1]);
        }
    }
}

JavaScript

function twoOdd(arr) {
    let xors = 0;
    for (const x of arr) xors ^= x;     // = x ^ y
    const sn = xors & -xors;            // rightmost set bit (same as xors & ~(xors - 1))
    let res1 = 0, res2 = 0;
    for (const x of arr) {
        if (x & sn) res1 ^= x;          // group with the bit set
        else        res2 ^= x;          // group with the bit clear
    }
    return [Math.min(res1, res2), Math.max(res1, res2)];
}

for (const arr of [[3, 4, 3, 4, 5, 4, 4, 6, 7, 7], [20, 15, 20, 16]]) {
    const [a, b] = twoOdd(arr);
    console.log(arr.join(" "), "->", a, b);
}

Output

3 4 3 4 5 4 4 6 7 7 -> 5 6
20 15 20 16 -> 15 16

Time O(n) · Space O(1)

Power set using bitmasks

The counter's bits choose the elements

s = "abc", n = 3, masks 0 … 7       (bit 0 ↔ a, bit 1 ↔ b, bit 2 ↔ c)

i    c b a    subset
0    0 0 0    {}
1    0 0 1    {a}
2    0 1 0    {b}
3    0 1 1    {a,b}
4    1 0 0    {c}
5    1 0 1    {a,c}
6    1 1 0    {b,c}
7    1 1 1    {a,b,c}

Python

def power_set(s):
    n = len(s)
    for i in range(1 << n):                      # 2^n masks
        chosen = [s[j] for j in range(n) if i & (1 << j)]   # bit j set → take s[j]
        print(format(i, f"0{n}b"), "-> {" + ",".join(chosen) + "}")

power_set("abc")

C++

#include <iostream>
#include <string>
using namespace std;

void powerSet(const string& s) {
    int n = s.size();
    for (int i = 0; i < (1 << n); i++) {        // 2^n masks
        string mask, chosen;
        for (int j = n - 1; j >= 0; j--) mask += ((i >> j) & 1) ? '1' : '0';
        for (int j = 0; j < n; j++)
            if (i & (1 << j)) {                  // bit j set → take s[j]
                if (!chosen.empty()) chosen += ',';
                chosen += s[j];
            }
        cout << mask << " -> {" << chosen << "}\n";
    }
}

int main() { powerSet("abc"); }

Java

public class Main {
    static void powerSet(String s) {
        int n = s.length();
        for (int i = 0; i < (1 << n); i++) {    // 2^n masks
            StringBuilder mask = new StringBuilder(), chosen = new StringBuilder();
            for (int j = n - 1; j >= 0; j--) mask.append((i >> j) & 1);
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) != 0) {       // bit j set → take s[j]
                    if (chosen.length() > 0) chosen.append(',');
                    chosen.append(s.charAt(j));
                }
            System.out.println(mask + " -> {" + chosen + "}");
        }
    }

    public static void main(String[] args) { powerSet("abc"); }
}

JavaScript

function powerSet(s) {
    const n = s.length;
    for (let i = 0; i < (1 << n); i++) {        // 2^n masks
        const chosen = [];
        for (let j = 0; j < n; j++)
            if (i & (1 << j)) chosen.push(s[j]); // bit j set → take s[j]
        console.log(i.toString(2).padStart(n, "0"), "-> {" + chosen.join(",") + "}");
    }
}

powerSet("abc");

Output

000 -> {}
001 -> {a}
010 -> {b}
011 -> {a,b}
100 -> {c}
101 -> {a,c}
110 -> {b,c}
111 -> {a,b,c}

Time O(2^n · n) · Space O(n) for the current subset

Interview Q&A

Why does n & (n - 1) clear the rightmost set bit?

How do you check if two integers have opposite signs without comparing them?

What is the difference between >> and >>>?

Every element appears three times except one. Does XOR still work?

How would you find the missing number in 1…n with one slot missing, without extra space?

When is the lookup-table popcount actually better than Kernighan's loop?