Skip to main content
CodePeet

CodePeet 700 Complete DSA Sheet

Introduction to Bit Manipulation

Editorial

The bit count that never ends

Counting Set Bits asks how many 1s a number has in binary. The loop everyone writes looks at the last bit with n & 1, shifts it away with n >>= 1, and stops when n is 0. On 13 it's right. Here it is on 13, then on −1, in every language the judge runs:

def count_bits(n):                    # look at the last bit, shift it away, until n is 0
    count = 0
    while n != 0:
        count += n & 1
        n >>= 1
    return count


print(count_bits(13), flush=True)
print(count_bits(-1), flush=True)

# 3
# (no second line: still looping when the judge stopped it after 2 s)
public class Main {
    static int countBits(int n) {         // look at the last bit, shift it away, until n is 0
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countBits(13));
        System.out.println(countBits(-1));
    }
}

// 3
// (no second line: still looping when the judge stopped it after 2 s)
#include <bits/stdc++.h>
using namespace std;

int countBits(int n) {                // look at the last bit, shift it away, until n is 0
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int main() {
    cout << countBits(13) << endl;
    cout << countBits(-1) << endl;
}

// 3
// (no second line: the program crashed with a trap)
function countBits(n) {               // look at the last bit, shift it away, until n is 0
    let count = 0;
    while (n !== 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

console.log(countBits(13));
console.log(countBits(-1));

// 3
// (no second line: still looping when the judge stopped it after 2 s)
function countBits(n: number): number {   // look at the last bit, shift it away, until n is 0
    let count = 0;
    while (n !== 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

console.log(countBits(13));
console.log(countBits(-1));

// 3
// (no second line: still looping when the judge stopped it after 2 s)
using System;

class Program {
    static int CountBits(int n) {         // look at the last bit, shift it away, until n is 0
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }

    static void Main() {
        Console.WriteLine(CountBits(13));
        Console.WriteLine(CountBits(-1));
    }
}

// 3
// (no second line: still looping when the judge stopped it after 2 s)
package main

import "fmt"

func countBits(n int) int {           // look at the last bit, shift it away, until n is 0
	count := 0
	for n != 0 {
		count += n & 1
		n >>= 1
	}
	return count
}

func main() {
	fmt.Println(countBits(13))
	fmt.Println(countBits(-1))
}

// 3
// (no second line: still looping when the judge stopped it after 2 s)

Every one printed 3 for 13. On −1, six of them never printed a second line: the judge stopped them after 2 seconds, still looping. C++ crashed instead. A loop that never ends and changes nothing you can see is undefined behaviour in C++, and the compiler put a trap there.

−1 is all 1s. A right shift with >> keeps a negative number negative by copying the sign bit in from the left, so −1 >> 1 is −1 again, and n never reaches 0. Python's integers have no width at all: its −1 has 1s forever to the left. This lesson is about how numbers are stored as bits, the operators that work on them, and the handful of moves most bit problems are built from.

Two dashed panels for the 32 bits of −1, every cell a 1, the leftmost one orange and labelled sign. Left, crossed, −1 >> 1: the row shifts one place right, the bit that falls off the right end is greyed, and an orange arrow brings the sign bit back in on the left: 32 ones again, = −1, so the loop never reaches 0. Right, ticked, −1 >>> 1: the same shift with a green 0 coming in on the left: 0 then 31 ones, = 2,147,483,647, and the loop ends after 32 steps. Focal line: >> copies the sign bit; >>> brings in a 0. Title: the sign bit copies itself.

The fix in each language

Count the 32 bits, not "until n is 0": bring a 0 in from the left. Java, JavaScript, TypeScript and C# have >>> for that. C++ and Go use an unsigned type, where >> always brings in 0s. Python has neither, so it keeps only the low 32 bits of n first:

def count_bits(n):
    n &= 0xFFFFFFFF                   # Python's -1 has 1s forever to the left: keep the low 32 bits
    count = 0
    while n != 0:
        count += n & 1
        n >>= 1
    return count


print(count_bits(13))
print(count_bits(-1))

# 3
# 32
public class Main {
    static int countBits(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>>= 1;                         // >>> brings in a 0 from the left; >> copies the sign bit
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countBits(13));
        System.out.println(countBits(-1));
    }
}

// 3
// 32
#include <bits/stdc++.h>
using namespace std;

int countBits(unsigned n) {           // unsigned: >> brings in a 0 from the left
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int main() {
    cout << countBits(13) << "\n";
    cout << countBits(-1) << "\n";
}

// 3
// 32
function countBits(n) {
    let count = 0;
    while (n !== 0) {
        count += n & 1;
        n >>>= 1;                         // >>> brings in a 0 from the left; >> copies the sign bit
    }
    return count;
}

console.log(countBits(13));
console.log(countBits(-1));

// 3
// 32
function countBits(n: number): number {
    let count = 0;
    while (n !== 0) {
        count += n & 1;
        n >>>= 1;                         // >>> brings in a 0 from the left; >> copies the sign bit
    }
    return count;
}

console.log(countBits(13));
console.log(countBits(-1));

// 3
// 32
using System;

class Program {
    static int CountBits(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>>= 1;                         // >>> brings in a 0 from the left; >> copies the sign bit
        }
        return count;
    }

    static void Main() {
        Console.WriteLine(CountBits(13));
        Console.WriteLine(CountBits(-1));
    }
}

// 3
// 32
package main

import "fmt"

func countBits(n uint32) int {        // uint32: >> brings in a 0 from the left
	count := 0
	for n != 0 {
		count += int(n & 1)
		n >>= 1
	}
	return count
}

func main() {
	minusOne := int32(-1)
	fmt.Println(countBits(13))
	fmt.Println(countBits(uint32(minusOne)))
}

// 3
// 32

Now −1 has 32 ones, in all seven.

Bits and negative numbers

Each bit is a power of two: 13 is 8 + 4 + 1, written 1101. A negative number is stored in two's complement: flip every bit of 5 and add 1, and you get −5. Its top bit is 1, and read as a value, the top bit of a 32-bit integer counts −2³¹ while the other 31 add up as usual. Printing the 32 bits of 13 and −5, then 1 << 31, the number with only the top bit set:

for n in (13, -5):
    print(format(n & 0xFFFFFFFF, "032b"))      # the low 32 bits of n
print(1 << 31)

# 00000000000000000000000000001101
# 11111111111111111111111111111011
# 2147483648
public class Main {
    public static void main(String[] args) {
        for (int n : new int[] {13, -5})
            System.out.println(String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0'));
        System.out.println(1 << 31);
    }
}

// 00000000000000000000000000001101
// 11111111111111111111111111111011
// -2147483648
#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int n : {13, -5})
        cout << bitset<32>(n) << "\n";
    cout << (1 << 31) << "\n";
}

// 00000000000000000000000000001101
// 11111111111111111111111111111011
// -2147483648
for (const n of [13, -5])
    console.log((n >>> 0).toString(2).padStart(32, "0"));   // >>> 0 reads n as 32 unsigned bits
console.log(1 << 31);

// 00000000000000000000000000001101
// 11111111111111111111111111111011
// -2147483648
for (const n of [13, -5])
    console.log((n >>> 0).toString(2).padStart(32, "0"));   // >>> 0 reads n as 32 unsigned bits
console.log(1 << 31);

// 00000000000000000000000000001101
// 11111111111111111111111111111011
// -2147483648
using System;

class Program {
    static void Main() {
        foreach (int n in new[] { 13, -5 })
            Console.WriteLine(Convert.ToString(n, 2).PadLeft(32, '0'));
        Console.WriteLine(1 << 31);
    }
}

// 00000000000000000000000000001101
// 11111111111111111111111111111011
// -2147483648
package main

import "fmt"

func main() {
	for _, n := range []int32{13, -5} {
		fmt.Printf("%032b\n", uint32(n))
	}
	fmt.Println(1 << 31)
}

// 00000000000000000000000000001101
// 11111111111111111111111111111011
// 2147483648

All seven printed the same 32 bits for 13 and for −5. They didn't agree on 1 << 31: Python and Go printed 2,147,483,648, the other five −2,147,483,648, because their int is 32 bits and bit 31 is the sign bit. JavaScript's numbers are doubles, but its bit operators work on 32-bit integers (JavaScript for DSA):

Language1 << 31Integer widthShift in a 0
Python2,147,483,648no limitnone: keep n & 0xFFFFFFFF
Java−2,147,483,64832 bits (long: 64)>>>
C++−2,147,483,64832 bits (long long: 64)an unsigned type
JavaScript−2,147,483,64832 bits in bit operators>>>
TypeScript−2,147,483,64832 bits in bit operators>>>
C#−2,147,483,64832 bits (long: 64)>>>, or uint
Go2,147,483,64864 bits (int here)uint32, uint64

The six operators

Four work bit by bit, on bits in the same position: AND keeps a 1 where both have one, OR where either does, XOR where exactly one does, and NOT flips every bit. The shifts move every bit left or right. On 12, 1100, and 10, 1010:

a, b = 12, 10                         # 1100 and 1010
print(f"{a} & {b} = {a & b}")         # 1 where both bits are 1
print(f"{a} | {b} = {a | b}")         # 1 where either is
print(f"{a} ^ {b} = {a ^ b}")         # 1 where they differ
print(f"~{a} = {~a}")                 # every bit flipped
print(f"{a} << 2 = {a << 2}")         # two places left: times 4
print(f"{a} >> 2 = {a >> 2}")         # two places right: divided by 4

# 12 & 10 = 8
# 12 | 10 = 14
# 12 ^ 10 = 6
# ~12 = -13
# 12 << 2 = 48
# 12 >> 2 = 3
public class Main {
    public static void main(String[] args) {
        int a = 12, b = 10;               // 1100 and 1010
        System.out.println(a + " & " + b + " = " + (a & b));   // 1 where both bits are 1
        System.out.println(a + " | " + b + " = " + (a | b));   // 1 where either is
        System.out.println(a + " ^ " + b + " = " + (a ^ b));   // 1 where they differ
        System.out.println("~" + a + " = " + (~a));            // every bit flipped
        System.out.println(a + " << 2 = " + (a << 2));         // two places left: times 4
        System.out.println(a + " >> 2 = " + (a >> 2));         // two places right: divided by 4
    }
}

// 12 & 10 = 8
// 12 | 10 = 14
// 12 ^ 10 = 6
// ~12 = -13
// 12 << 2 = 48
// 12 >> 2 = 3
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 12, b = 10;                   // 1100 and 1010
    cout << a << " & " << b << " = " << (a & b) << "\n";   // 1 where both bits are 1
    cout << a << " | " << b << " = " << (a | b) << "\n";   // 1 where either is
    cout << a << " ^ " << b << " = " << (a ^ b) << "\n";   // 1 where they differ
    cout << "~" << a << " = " << (~a) << "\n";             // every bit flipped
    cout << a << " << 2 = " << (a << 2) << "\n";           // two places left: times 4
    cout << a << " >> 2 = " << (a >> 2) << "\n";           // two places right: divided by 4
}

// 12 & 10 = 8
// 12 | 10 = 14
// 12 ^ 10 = 6
// ~12 = -13
// 12 << 2 = 48
// 12 >> 2 = 3
const a = 12, b = 10;                 // 1100 and 1010
console.log(`${a} & ${b} = ${a & b}`);   // 1 where both bits are 1
console.log(`${a} | ${b} = ${a | b}`);   // 1 where either is
console.log(`${a} ^ ${b} = ${a ^ b}`);   // 1 where they differ
console.log(`~${a} = ${~a}`);            // every bit flipped
console.log(`${a} << 2 = ${a << 2}`);    // two places left: times 4
console.log(`${a} >> 2 = ${a >> 2}`);    // two places right: divided by 4

// 12 & 10 = 8
// 12 | 10 = 14
// 12 ^ 10 = 6
// ~12 = -13
// 12 << 2 = 48
// 12 >> 2 = 3
const a: number = 12, b: number = 10;   // 1100 and 1010
console.log(`${a} & ${b} = ${a & b}`);   // 1 where both bits are 1
console.log(`${a} | ${b} = ${a | b}`);   // 1 where either is
console.log(`${a} ^ ${b} = ${a ^ b}`);   // 1 where they differ
console.log(`~${a} = ${~a}`);            // every bit flipped
console.log(`${a} << 2 = ${a << 2}`);    // two places left: times 4
console.log(`${a} >> 2 = ${a >> 2}`);    // two places right: divided by 4

// 12 & 10 = 8
// 12 | 10 = 14
// 12 ^ 10 = 6
// ~12 = -13
// 12 << 2 = 48
// 12 >> 2 = 3
using System;

class Program {
    static void Main() {
        int a = 12, b = 10;               // 1100 and 1010
        Console.WriteLine($"{a} & {b} = {a & b}");   // 1 where both bits are 1
        Console.WriteLine($"{a} | {b} = {a | b}");   // 1 where either is
        Console.WriteLine($"{a} ^ {b} = {a ^ b}");   // 1 where they differ
        Console.WriteLine($"~{a} = {~a}");           // every bit flipped
        Console.WriteLine($"{a} << 2 = {a << 2}");   // two places left: times 4
        Console.WriteLine($"{a} >> 2 = {a >> 2}");   // two places right: divided by 4
    }
}

// 12 & 10 = 8
// 12 | 10 = 14
// 12 ^ 10 = 6
// ~12 = -13
// 12 << 2 = 48
// 12 >> 2 = 3
package main

import "fmt"

func main() {
	a, b := 12, 10                      // 1100 and 1010
	fmt.Printf("%d & %d = %d\n", a, b, a&b) // 1 where both bits are 1
	fmt.Printf("%d | %d = %d\n", a, b, a|b) // 1 where either is
	fmt.Printf("%d ^ %d = %d\n", a, b, a^b) // 1 where they differ
	fmt.Printf("~%d = %d\n", a, ^a)         // every bit flipped: Go writes it ^a
	fmt.Printf("%d << 2 = %d\n", a, a<<2)   // two places left: times 4
	fmt.Printf("%d >> 2 = %d\n", a, a>>2)   // two places right: divided by 4
}

// 12 & 10 = 8
// 12 | 10 = 14
// 12 ^ 10 = 6
// ~12 = -13
// 12 << 2 = 48
// 12 >> 2 = 3

~12 is −13: flipping every bit of n gives −(n + 1), in every language, since n + ~n is all 1s, which is −1. A left shift by k multiplies by 2ᵏ while the result fits; a right shift by k divides by 2ᵏ and rounds down, even below zero: −7 >> 1 is −4 in all seven (Mistakes that cost an interview has why that isn't always −7 / 2).

One bit at a time

Most bit problems read or change one bit. The tool is a mask: a number with 1s only where you want to act, usually 1 << k for bit k, counting from 0 on the right. AND with it reads the bit, OR sets it, AND with the flipped mask clears it, and XOR toggles it. On 22, 10110:

def bits(x):                          # x as 5 bits
    return format(x, "05b")


n = 22
print(f"n = {bits(n)} ({n})")
print(f"bit 1 is {(n >> 1) & 1}, bit 0 is {(n >> 0) & 1}")   # check: shift bit k down, keep it
print(f"set bit 0:    {bits(n | (1 << 0))}")                # OR with the mask: that bit becomes 1
print(f"clear bit 2:  {bits(n & ~(1 << 2))}")               # AND with the flipped mask: it becomes 0
print(f"toggle bit 4: {bits(n ^ (1 << 4))}")                # XOR with the mask: it flips
m = 23
print(f"lowest 0 of {bits(m)} set: {bits(m | (m + 1))}")    # m + 1 turns the lowest 0 into a 1

# n = 10110 (22)
# bit 1 is 1, bit 0 is 0
# set bit 0:    10111
# clear bit 2:  10010
# toggle bit 4: 00110
# lowest 0 of 10111 set: 11111
public class Main {
    static String bits(int x) {           // x as 5 bits
        return String.format("%5s", Integer.toBinaryString(x)).replace(' ', '0');
    }

    public static void main(String[] args) {
        int n = 22;
        System.out.println("n = " + bits(n) + " (" + n + ")");
        System.out.println("bit 1 is " + ((n >> 1) & 1) + ", bit 0 is " + ((n >> 0) & 1));   // check
        System.out.println("set bit 0:    " + bits(n | (1 << 0)));    // OR with the mask: that bit becomes 1
        System.out.println("clear bit 2:  " + bits(n & ~(1 << 2)));   // AND with the flipped mask: it becomes 0
        System.out.println("toggle bit 4: " + bits(n ^ (1 << 4)));    // XOR with the mask: it flips
        int m = 23;
        System.out.println("lowest 0 of " + bits(m) + " set: " + bits(m | (m + 1)));   // m + 1: lowest 0 to 1
    }
}

// n = 10110 (22)
// bit 1 is 1, bit 0 is 0
// set bit 0:    10111
// clear bit 2:  10010
// toggle bit 4: 00110
// lowest 0 of 10111 set: 11111
#include <bits/stdc++.h>
using namespace std;

string bits(int x) {                  // x as 5 bits
    return bitset<5>(x).to_string();
}

int main() {
    int n = 22;
    cout << "n = " << bits(n) << " (" << n << ")\n";
    cout << "bit 1 is " << ((n >> 1) & 1) << ", bit 0 is " << ((n >> 0) & 1) << "\n";   // check
    cout << "set bit 0:    " << bits(n | (1 << 0)) << "\n";    // OR with the mask: that bit becomes 1
    cout << "clear bit 2:  " << bits(n & ~(1 << 2)) << "\n";   // AND with the flipped mask: it becomes 0
    cout << "toggle bit 4: " << bits(n ^ (1 << 4)) << "\n";    // XOR with the mask: it flips
    int m = 23;
    cout << "lowest 0 of " << bits(m) << " set: " << bits(m | (m + 1)) << "\n";   // m + 1: lowest 0 to 1
}

// n = 10110 (22)
// bit 1 is 1, bit 0 is 0
// set bit 0:    10111
// clear bit 2:  10010
// toggle bit 4: 00110
// lowest 0 of 10111 set: 11111
const bits = (x) => x.toString(2).padStart(5, "0");   // x as 5 bits

const n = 22;
console.log(`n = ${bits(n)} (${n})`);
console.log(`bit 1 is ${(n >> 1) & 1}, bit 0 is ${(n >> 0) & 1}`);   // check: shift bit k down, keep it
console.log(`set bit 0:    ${bits(n | (1 << 0))}`);                // OR with the mask: that bit becomes 1
console.log(`clear bit 2:  ${bits(n & ~(1 << 2))}`);               // AND with the flipped mask: it becomes 0
console.log(`toggle bit 4: ${bits(n ^ (1 << 4))}`);                // XOR with the mask: it flips
const m = 23;
console.log(`lowest 0 of ${bits(m)} set: ${bits(m | (m + 1))}`);    // m + 1 turns the lowest 0 into a 1

// n = 10110 (22)
// bit 1 is 1, bit 0 is 0
// set bit 0:    10111
// clear bit 2:  10010
// toggle bit 4: 00110
// lowest 0 of 10111 set: 11111
const bits = (x: number): string => x.toString(2).padStart(5, "0");   // x as 5 bits

const n: number = 22;
console.log(`n = ${bits(n)} (${n})`);
console.log(`bit 1 is ${(n >> 1) & 1}, bit 0 is ${(n >> 0) & 1}`);   // check: shift bit k down, keep it
console.log(`set bit 0:    ${bits(n | (1 << 0))}`);                // OR with the mask: that bit becomes 1
console.log(`clear bit 2:  ${bits(n & ~(1 << 2))}`);               // AND with the flipped mask: it becomes 0
console.log(`toggle bit 4: ${bits(n ^ (1 << 4))}`);                // XOR with the mask: it flips
const m: number = 23;
console.log(`lowest 0 of ${bits(m)} set: ${bits(m | (m + 1))}`);    // m + 1 turns the lowest 0 into a 1

// n = 10110 (22)
// bit 1 is 1, bit 0 is 0
// set bit 0:    10111
// clear bit 2:  10010
// toggle bit 4: 00110
// lowest 0 of 10111 set: 11111
using System;

class Program {
    static string Bits(int x) => Convert.ToString(x, 2).PadLeft(5, '0');   // x as 5 bits

    static void Main() {
        int n = 22;
        Console.WriteLine($"n = {Bits(n)} ({n})");
        Console.WriteLine($"bit 1 is {(n >> 1) & 1}, bit 0 is {(n >> 0) & 1}");   // check
        Console.WriteLine($"set bit 0:    {Bits(n | (1 << 0))}");    // OR with the mask: that bit becomes 1
        Console.WriteLine($"clear bit 2:  {Bits(n & ~(1 << 2))}");   // AND with the flipped mask: it becomes 0
        Console.WriteLine($"toggle bit 4: {Bits(n ^ (1 << 4))}");    // XOR with the mask: it flips
        int m = 23;
        Console.WriteLine($"lowest 0 of {Bits(m)} set: {Bits(m | (m + 1))}");   // m + 1: lowest 0 to 1
    }
}

// n = 10110 (22)
// bit 1 is 1, bit 0 is 0
// set bit 0:    10111
// clear bit 2:  10010
// toggle bit 4: 00110
// lowest 0 of 10111 set: 11111
package main

import "fmt"

func bits(x int) string {             // x as 5 bits
	return fmt.Sprintf("%05b", x)
}

func main() {
	n := 22
	fmt.Printf("n = %s (%d)\n", bits(n), n)
	fmt.Printf("bit 1 is %d, bit 0 is %d\n", (n>>1)&1, (n>>0)&1) // check: shift bit k down, keep it
	fmt.Println("set bit 0:   ", bits(n|(1<<0)))                // OR with the mask: that bit becomes 1
	fmt.Println("clear bit 2: ", bits(n&^(1<<2)))               // AND NOT, Go's &^: it becomes 0
	fmt.Println("toggle bit 4:", bits(n^(1<<4)))                // XOR with the mask: it flips
	m := 23
	fmt.Printf("lowest 0 of %s set: %s\n", bits(m), bits(m|(m+1))) // m + 1 turns the lowest 0 into a 1
}

// n = 10110 (22)
// bit 1 is 1, bit 0 is 0
// set bit 0:    10111
// clear bit 2:  10010
// toggle bit 4: 00110
// lowest 0 of 10111 set: 11111
A dashed band with 10110 (22) as five tiles numbered 4 to 0, then four dashed cards in a row, each with a numbered pill. 1, check bit 1: (n >> 1) & 1 = 1. 2, set bit 0: n | (1 << 0), the result 10111 with bit 0 in green. 3, clear bit 2: n & ~(1 << 2), the result 10010 with bit 2 in green. 4, toggle bit 4: n ^ (1 << 4), the result 00110 with bit 4 in green. Focal line: one mask, 1 << k; the operator decides the job. Title: one mask, four jobs.

Those lines answer Check K-th Bit and Bitwise Operations Overview. The last one is Toggle Rightmost Unset Bit: adding 1 to 10111 carries through its trailing 1s and turns the lowest 0 into a 1, giving 11000, and the OR with the original 10111 brings back the 1s the carry cleared: 11111.

The lowest set bit

x − 1 turns the lowest 1 of x into a 0 and the 0s below it into 1s, and leaves everything above alone. So x & (x − 1) is x without its lowest set bit. And −x is ~x + 1: every bit above the lowest 1 flipped, the lowest 1 and the 0s below it kept. So x & −x is the lowest set bit alone:

for x in (40, 12, 16, 1):
    print(f"{x}: x & (x - 1) = {x & (x - 1)}, x & -x = {x & -x}")
for n in (1, 16, 40, 0, -16):
    power = n > 0 and (n & (n - 1)) == 0  # one set bit, and positive
    print(f"{n}: {'a power of two' if power else 'no'}")
print("without n > 0, 0 passes:", "true" if (0 & (0 - 1)) == 0 else "false")

# 40: x & (x - 1) = 32, x & -x = 8
# 12: x & (x - 1) = 8, x & -x = 4
# 16: x & (x - 1) = 0, x & -x = 16
# 1: x & (x - 1) = 0, x & -x = 1
# 1: a power of two
# 16: a power of two
# 40: no
# 0: no
# -16: no
# without n > 0, 0 passes: true
public class Main {
    public static void main(String[] args) {
        for (int x : new int[] {40, 12, 16, 1})
            System.out.println(x + ": x & (x - 1) = " + (x & (x - 1)) + ", x & -x = " + (x & -x));
        for (int n : new int[] {1, 16, 40, 0, -16}) {
            boolean power = n > 0 && (n & (n - 1)) == 0;   // one set bit, and positive
            System.out.println(n + ": " + (power ? "a power of two" : "no"));
        }
        int zero = 0;
        System.out.println("without n > 0, 0 passes: " + ((zero & (zero - 1)) == 0));
    }
}

// 40: x & (x - 1) = 32, x & -x = 8
// 12: x & (x - 1) = 8, x & -x = 4
// 16: x & (x - 1) = 0, x & -x = 16
// 1: x & (x - 1) = 0, x & -x = 1
// 1: a power of two
// 16: a power of two
// 40: no
// 0: no
// -16: no
// without n > 0, 0 passes: true
#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int x : {40, 12, 16, 1})
        cout << x << ": x & (x - 1) = " << (x & (x - 1)) << ", x & -x = " << (x & -x) << "\n";
    for (int n : {1, 16, 40, 0, -16}) {
        bool power = n > 0 && (n & (n - 1)) == 0;   // one set bit, and positive
        cout << n << ": " << (power ? "a power of two" : "no") << "\n";
    }
    int zero = 0;
    cout << "without n > 0, 0 passes: " << boolalpha << ((zero & (zero - 1)) == 0) << "\n";
}

// 40: x & (x - 1) = 32, x & -x = 8
// 12: x & (x - 1) = 8, x & -x = 4
// 16: x & (x - 1) = 0, x & -x = 16
// 1: x & (x - 1) = 0, x & -x = 1
// 1: a power of two
// 16: a power of two
// 40: no
// 0: no
// -16: no
// without n > 0, 0 passes: true
for (const x of [40, 12, 16, 1])
    console.log(`${x}: x & (x - 1) = ${x & (x - 1)}, x & -x = ${x & -x}`);
for (const n of [1, 16, 40, 0, -16]) {
    const power = n > 0 && (n & (n - 1)) === 0;   // one set bit, and positive
    console.log(`${n}: ${power ? "a power of two" : "no"}`);
}
const zero = 0;
console.log(`without n > 0, 0 passes: ${(zero & (zero - 1)) === 0}`);

// 40: x & (x - 1) = 32, x & -x = 8
// 12: x & (x - 1) = 8, x & -x = 4
// 16: x & (x - 1) = 0, x & -x = 16
// 1: x & (x - 1) = 0, x & -x = 1
// 1: a power of two
// 16: a power of two
// 40: no
// 0: no
// -16: no
// without n > 0, 0 passes: true
for (const x of [40, 12, 16, 1])
    console.log(`${x}: x & (x - 1) = ${x & (x - 1)}, x & -x = ${x & -x}`);
for (const n of [1, 16, 40, 0, -16]) {
    const power: boolean = n > 0 && (n & (n - 1)) === 0;   // one set bit, and positive
    console.log(`${n}: ${power ? "a power of two" : "no"}`);
}
const zero: number = 0;
console.log(`without n > 0, 0 passes: ${(zero & (zero - 1)) === 0}`);

// 40: x & (x - 1) = 32, x & -x = 8
// 12: x & (x - 1) = 8, x & -x = 4
// 16: x & (x - 1) = 0, x & -x = 16
// 1: x & (x - 1) = 0, x & -x = 1
// 1: a power of two
// 16: a power of two
// 40: no
// 0: no
// -16: no
// without n > 0, 0 passes: true
using System;

class Program {
    static void Main() {
        foreach (int x in new[] { 40, 12, 16, 1 })
            Console.WriteLine($"{x}: x & (x - 1) = {x & (x - 1)}, x & -x = {x & -x}");
        foreach (int n in new[] { 1, 16, 40, 0, -16 }) {
            bool power = n > 0 && (n & (n - 1)) == 0;   // one set bit, and positive
            Console.WriteLine($"{n}: {(power ? "a power of two" : "no")}");
        }
        int zero = 0;
        Console.WriteLine($"without n > 0, 0 passes: {((zero & (zero - 1)) == 0 ? "true" : "false")}");
    }
}

// 40: x & (x - 1) = 32, x & -x = 8
// 12: x & (x - 1) = 8, x & -x = 4
// 16: x & (x - 1) = 0, x & -x = 16
// 1: x & (x - 1) = 0, x & -x = 1
// 1: a power of two
// 16: a power of two
// 40: no
// 0: no
// -16: no
// without n > 0, 0 passes: true
package main

import "fmt"

func main() {
	for _, x := range []int{40, 12, 16, 1} {
		fmt.Printf("%d: x & (x - 1) = %d, x & -x = %d\n", x, x&(x-1), x&-x)
	}
	for _, n := range []int{1, 16, 40, 0, -16} {
		power := n > 0 && n&(n-1) == 0 // one set bit, and positive
		if power {
			fmt.Printf("%d: a power of two\n", n)
		} else {
			fmt.Printf("%d: no\n", n)
		}
	}
	zero := 0
	fmt.Println("without n > 0, 0 passes:", zero&(zero-1) == 0)
}

// 40: x & (x - 1) = 32, x & -x = 8
// 12: x & (x - 1) = 8, x & -x = 4
// 16: x & (x - 1) = 0, x & -x = 16
// 1: x & (x - 1) = 0, x & -x = 1
// 1: a power of two
// 16: a power of two
// 40: no
// 0: no
// -16: no
// without n > 0, 0 passes: true
Two dashed panels for 40 in binary, 101000, its lowest 1 orange. Left, x & (x − 1): the rows 101000, then x − 1 = 100111 with the lowest 1 and the 0s below it flipped, then AND = 100000 (32), the lowest 1 gone. Right, x & −x: the rows 101000, then −x = …011000 with every bit above the lowest 1 flipped, then AND = 001000 (8), only the lowest 1 left. Focal line: x & (x − 1) clears it; x & −x keeps only it. Title: the lowest set bit.

A power of two has exactly one set bit, so x & (x − 1) is 0 for it and for nothing else above 0: that's Power of Two in one line. The n > 0 matters: 0 passes the test without it.

Counting the 1s

The shift loop takes one step for every bit up to the highest 1. Repeating x & (x − 1) takes one step for every 1, which is Brian Kernighan's way:

def shifting(n):                      # one step per bit up to the highest 1
    count = steps = 0
    while n != 0:
        count += n & 1
        n >>= 1
        steps += 1
    return count, steps


def kernighan(n):                     # one step per 1: n & (n - 1) clears the lowest
    count = 0
    while n != 0:
        n &= n - 1
        count += 1
    return count


for n in (13, 2147483647, 1073741824):
    ones, steps = shifting(n)
    print(f"{n}: {ones} ones; shifting took {steps} steps, n & (n - 1) took {kernighan(n)}")
print("built-in:", *(n.bit_count() for n in (13, 2147483647, 1073741824)))

# 13: 3 ones; shifting took 4 steps, n & (n - 1) took 3
# 2147483647: 31 ones; shifting took 31 steps, n & (n - 1) took 31
# 1073741824: 1 ones; shifting took 31 steps, n & (n - 1) took 1
# built-in: 3 31 1
public class Main {
    static int[] shifting(int n) {        // one step per bit up to the highest 1
        int count = 0, steps = 0;
        while (n != 0) {
            count += n & 1;
            n >>>= 1;
            steps++;
        }
        return new int[] {count, steps};
    }

    static int kernighan(int n) {         // one step per 1: n & (n - 1) clears the lowest
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] values = {13, 2147483647, 1073741824};
        for (int n : values) {
            int[] r = shifting(n);
            System.out.println(n + ": " + r[0] + " ones; shifting took " + r[1] + " steps, n & (n - 1) took "
                + kernighan(n));
        }
        StringBuilder line = new StringBuilder("built-in:");
        for (int n : values) line.append(" ").append(Integer.bitCount(n));
        System.out.println(line);
    }
}

// 13: 3 ones; shifting took 4 steps, n & (n - 1) took 3
// 2147483647: 31 ones; shifting took 31 steps, n & (n - 1) took 31
// 1073741824: 1 ones; shifting took 31 steps, n & (n - 1) took 1
// built-in: 3 31 1
#include <bits/stdc++.h>
using namespace std;

pair<int, int> shifting(unsigned n) {  // one step per bit up to the highest 1
    int count = 0, steps = 0;
    while (n != 0) {
        count += n & 1;
        n >>= 1;
        steps++;
    }
    return {count, steps};
}

int kernighan(unsigned n) {            // one step per 1: n & (n - 1) clears the lowest
    int count = 0;
    while (n != 0) {
        n &= n - 1;
        count++;
    }
    return count;
}

int main() {
    unsigned values[] = {13, 2147483647, 1073741824};
    for (unsigned n : values) {
        auto [ones, steps] = shifting(n);
        cout << n << ": " << ones << " ones; shifting took " << steps << " steps, n & (n - 1) took "
             << kernighan(n) << "\n";
    }
    cout << "built-in:";
    for (unsigned n : values) cout << " " << popcount(n);
    cout << "\n";
}

// 13: 3 ones; shifting took 4 steps, n & (n - 1) took 3
// 2147483647: 31 ones; shifting took 31 steps, n & (n - 1) took 31
// 1073741824: 1 ones; shifting took 31 steps, n & (n - 1) took 1
// built-in: 3 31 1
function shifting(n) {                // one step per bit up to the highest 1
    let count = 0, steps = 0;
    while (n !== 0) {
        count += n & 1;
        n >>>= 1;
        steps++;
    }
    return [count, steps];
}

function kernighan(n) {               // one step per 1: n & (n - 1) clears the lowest
    let count = 0;
    while (n !== 0) {
        n &= n - 1;
        count++;
    }
    return count;
}

for (const n of [13, 2147483647, 1073741824]) {
    const [ones, steps] = shifting(n);
    console.log(`${n}: ${ones} ones; shifting took ${steps} steps, n & (n - 1) took ${kernighan(n)}`);
}

// 13: 3 ones; shifting took 4 steps, n & (n - 1) took 3
// 2147483647: 31 ones; shifting took 31 steps, n & (n - 1) took 31
// 1073741824: 1 ones; shifting took 31 steps, n & (n - 1) took 1
function shifting(n: number): [number, number] {   // one step per bit up to the highest 1
    let count = 0, steps = 0;
    while (n !== 0) {
        count += n & 1;
        n >>>= 1;
        steps++;
    }
    return [count, steps];
}

function kernighan(n: number): number {   // one step per 1: n & (n - 1) clears the lowest
    let count = 0;
    while (n !== 0) {
        n &= n - 1;
        count++;
    }
    return count;
}

for (const n of [13, 2147483647, 1073741824]) {
    const [ones, steps] = shifting(n);
    console.log(`${n}: ${ones} ones; shifting took ${steps} steps, n & (n - 1) took ${kernighan(n)}`);
}

// 13: 3 ones; shifting took 4 steps, n & (n - 1) took 3
// 2147483647: 31 ones; shifting took 31 steps, n & (n - 1) took 31
// 1073741824: 1 ones; shifting took 31 steps, n & (n - 1) took 1
using System;
using System.Numerics;

class Program {
    static (int, int) Shifting(uint n) {  // one step per bit up to the highest 1
        int count = 0, steps = 0;
        while (n != 0) {
            count += (int)(n & 1);
            n >>= 1;
            steps++;
        }
        return (count, steps);
    }

    static int Kernighan(uint n) {        // one step per 1: n & (n - 1) clears the lowest
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }

    static void Main() {
        uint[] values = { 13, 2147483647, 1073741824 };
        foreach (uint n in values) {
            var (ones, steps) = Shifting(n);
            Console.WriteLine($"{n}: {ones} ones; shifting took {steps} steps, n & (n - 1) took {Kernighan(n)}");
        }
        Console.WriteLine("built-in: " + string.Join(" ", Array.ConvertAll(values, n => BitOperations.PopCount(n))));
    }
}

// 13: 3 ones; shifting took 4 steps, n & (n - 1) took 3
// 2147483647: 31 ones; shifting took 31 steps, n & (n - 1) took 31
// 1073741824: 1 ones; shifting took 31 steps, n & (n - 1) took 1
// built-in: 3 31 1
package main

import (
	"fmt"
	"math/bits"
)

func shifting(n uint32) (int, int) { // one step per bit up to the highest 1
	count, steps := 0, 0
	for n != 0 {
		count += int(n & 1)
		n >>= 1
		steps++
	}
	return count, steps
}

func kernighan(n uint32) int {       // one step per 1: n & (n - 1) clears the lowest
	count := 0
	for n != 0 {
		n &= n - 1
		count++
	}
	return count
}

func main() {
	values := []uint32{13, 2147483647, 1073741824}
	for _, n := range values {
		ones, steps := shifting(n)
		fmt.Printf("%d: %d ones; shifting took %d steps, n & (n - 1) took %d\n", n, ones, steps, kernighan(n))
	}
	fmt.Print("built-in:")
	for _, n := range values {
		fmt.Print(" ", bits.OnesCount32(n))
	}
	fmt.Println()
}

// 13: 3 ones; shifting took 4 steps, n & (n - 1) took 3
// 2147483647: 31 ones; shifting took 31 steps, n & (n - 1) took 31
// 1073741824: 1 ones; shifting took 31 steps, n & (n - 1) took 1
// built-in: 3 31 1

On 2³⁰ the shift loop took 31 steps for its one 1; n & (n − 1) took 1. Every language but JavaScript and TypeScript also has a built-in, which the five printed on the last line:

LanguageBuilt-inTakes
Pythonn.bit_count()int (3.10 and later)
JavaInteger.bitCount(n)int; Long.bitCount for long
C++popcount(n)an unsigned type (C++20)
JavaScriptnonecount with n & (n − 1)
TypeScriptnonecount with n & (n − 1)
C#BitOperations.PopCount(n)uint or ulong
Gobits.OnesCount32(n)uint32; OnesCount64 for 64

Counting Bits wants the count for every i from 0 to n. i >> 1 is i without its last bit, so it's smaller and its count is already known: ones[i] = ones[i >> 1] + (i & 1), all n + 1 counts in O(n). And Minimum Bit Flips to Convert Number counts the bits where two numbers differ, which are the 1s of their XOR:

def counting_bits(n):                 # the 1s of every i from 0 to n
    ones = [0] * (n + 1)
    for i in range(1, n + 1):
        ones[i] = ones[i >> 1] + (i & 1)   # i is i >> 1 with one more bit on the right
    return ones


def bit_flips(start, goal):           # Minimum Bit Flips: the bits where they differ
    x, count = start ^ goal, 0
    while x != 0:
        x &= x - 1
        count += 1
    return count


print(*counting_bits(16))
print(bit_flips(10, 7))

# 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1
# 3
public class Main {
    static int[] countingBits(int n) {    // the 1s of every i from 0 to n
        int[] ones = new int[n + 1];
        for (int i = 1; i <= n; i++)
            ones[i] = ones[i >> 1] + (i & 1);   // i is i >> 1 with one more bit on the right
        return ones;
    }

    static int bitFlips(int start, int goal) {   // Minimum Bit Flips: the bits where they differ
        int x = start ^ goal, count = 0;
        while (x != 0) {
            x &= x - 1;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        StringBuilder line = new StringBuilder();
        for (int v : countingBits(16)) line.append(line.length() == 0 ? "" : " ").append(v);
        System.out.println(line);
        System.out.println(bitFlips(10, 7));
    }
}

// 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1
// 3
#include <bits/stdc++.h>
using namespace std;

vector<int> countingBits(int n) {      // the 1s of every i from 0 to n
    vector<int> ones(n + 1, 0);
    for (int i = 1; i <= n; i++)
        ones[i] = ones[i >> 1] + (i & 1);  // i is i >> 1 with one more bit on the right
    return ones;
}

int bitFlips(int start, int goal) {    // Minimum Bit Flips: the bits where they differ
    int x = start ^ goal, count = 0;
    while (x != 0) {
        x &= x - 1;
        count++;
    }
    return count;
}

int main() {
    vector<int> ones = countingBits(16);
    for (size_t i = 0; i < ones.size(); i++) cout << (i ? " " : "") << ones[i];
    cout << "\n" << bitFlips(10, 7) << "\n";
}

// 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1
// 3
function countingBits(n) {            // the 1s of every i from 0 to n
    const ones = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++)
        ones[i] = ones[i >> 1] + (i & 1);  // i is i >> 1 with one more bit on the right
    return ones;
}

function bitFlips(start, goal) {      // Minimum Bit Flips: the bits where they differ
    let x = start ^ goal, count = 0;
    while (x !== 0) {
        x &= x - 1;
        count++;
    }
    return count;
}

console.log(countingBits(16).join(" "));
console.log(bitFlips(10, 7));

// 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1
// 3
function countingBits(n: number): number[] {   // the 1s of every i from 0 to n
    const ones: number[] = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++)
        ones[i] = ones[i >> 1] + (i & 1);  // i is i >> 1 with one more bit on the right
    return ones;
}

function bitFlips(start: number, goal: number): number {   // Minimum Bit Flips: the bits where they differ
    let x = start ^ goal, count = 0;
    while (x !== 0) {
        x &= x - 1;
        count++;
    }
    return count;
}

console.log(countingBits(16).join(" "));
console.log(bitFlips(10, 7));

// 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1
// 3
using System;

class Program {
    static int[] CountingBits(int n) {    // the 1s of every i from 0 to n
        int[] ones = new int[n + 1];
        for (int i = 1; i <= n; i++)
            ones[i] = ones[i >> 1] + (i & 1);   // i is i >> 1 with one more bit on the right
        return ones;
    }

    static int BitFlips(int start, int goal) {   // Minimum Bit Flips: the bits where they differ
        int x = start ^ goal, count = 0;
        while (x != 0) {
            x &= x - 1;
            count++;
        }
        return count;
    }

    static void Main() {
        Console.WriteLine(string.Join(" ", CountingBits(16)));
        Console.WriteLine(BitFlips(10, 7));
    }
}

// 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1
// 3
package main

import (
	"fmt"
	"strings"
)

func countingBits(n int) []int {     // the 1s of every i from 0 to n
	ones := make([]int, n+1)
	for i := 1; i <= n; i++ {
		ones[i] = ones[i>>1] + i&1 // i is i >> 1 with one more bit on the right
	}
	return ones
}

func bitFlips(start, goal int) int { // Minimum Bit Flips: the bits where they differ
	x, count := start^goal, 0
	for x != 0 {
		x &= x - 1
		count++
	}
	return count
}

func main() {
	parts := []string{}
	for _, v := range countingBits(16) {
		parts = append(parts, fmt.Sprint(v))
	}
	fmt.Println(strings.Join(parts, " "))
	fmt.Println(bitFlips(10, 7))
}

// 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1
// 3

10 is 1010 and 7 is 0111: they differ in 3 places, so 3 flips.

Reversing bits

Reverse Bits moves bit i to bit 31 − i. Take n's last bit 32 times, each time pushing it onto the right end of the result, which shifts the earlier ones left:

def reverse_bits(n):                  # bit i of n becomes bit 31 - i
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)   # take n's last bit onto result's right end
        n >>= 1
    return result


print(reverse_bits(43261596))
print(reverse_bits(1))

# 964176192
# 2147483648
public class Main {
    static int reverseBits(int n) {       // bit i of n becomes bit 31 - i
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);   // take n's last bit onto result's right end
            n >>>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Integer.toUnsignedString(reverseBits(43261596)));   // read the 32 bits as unsigned
        System.out.println(Integer.toUnsignedString(reverseBits(1)));
    }
}

// 964176192
// 2147483648
#include <bits/stdc++.h>
using namespace std;

uint32_t reverseBits(uint32_t n) {     // bit i of n becomes bit 31 - i
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);  // take n's last bit onto result's right end
        n >>= 1;
    }
    return result;
}

int main() {
    cout << reverseBits(43261596) << "\n";
    cout << reverseBits(1) << "\n";
}

// 964176192
// 2147483648
function reverseBits(n) {             // bit i of n becomes bit 31 - i
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);  // take n's last bit onto result's right end
        n >>>= 1;
    }
    return result >>> 0;                  // read the 32 bits as unsigned
}

console.log(reverseBits(43261596));
console.log(reverseBits(1));

// 964176192
// 2147483648
function reverseBits(n: number): number {   // bit i of n becomes bit 31 - i
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);  // take n's last bit onto result's right end
        n >>>= 1;
    }
    return result >>> 0;                  // read the 32 bits as unsigned
}

console.log(reverseBits(43261596));
console.log(reverseBits(1));

// 964176192
// 2147483648
using System;

class Program {
    static uint ReverseBits(uint n) {     // bit i of n becomes bit 31 - i
        uint result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);   // take n's last bit onto result's right end
            n >>= 1;
        }
        return result;
    }

    static void Main() {
        Console.WriteLine(ReverseBits(43261596));
        Console.WriteLine(ReverseBits(1));
    }
}

// 964176192
// 2147483648
package main

import "fmt"

func reverseBits(n uint32) uint32 {   // bit i of n becomes bit 31 - i
	var result uint32
	for i := 0; i < 32; i++ {
		result = result<<1 | n&1 // take n's last bit onto result's right end
		n >>= 1
	}
	return result
}

func main() {
	fmt.Println(reverseBits(43261596))
	fmt.Println(reverseBits(1))
}

// 964176192
// 2147483648

43,261,596 reversed is 964,176,192, the problem's first example, and 1 reversed is 2,147,483,648: bit 0 became bit 31. Java has no unsigned int, so it keeps the 32 bits in an int and prints them with Integer.toUnsignedString; JavaScript and TypeScript read them back with >>> 0.

Flip the Bits. Reach the target value from the start value in as few moves as you can. Pick a bit and an operator, and watch the mask and the result in binary and decimal.

Flip the Bits: reach the target with masks, shifts and the lowest-bit moves

Spotting it

The clues: "binary", "bits", "set bits", "power of two", "flip", flags packed into one integer, a number read or built one bit at a time, or arithmetic "without +, −, × or ÷". Near misses:

  • Values that come in pairs, with one left over: XOR cancels the pairs (XOR Tricks).
  • Every subset of a small set, or a range ANDed together: masks as sets (Bitmasks and Bitwise Arithmetic).
  • A power computed by squaring reads its exponent bit by bit (Modular Arithmetic, Fast Power and Counting).
  • "Binary search" is about halving a range, not about bits (Introduction to Binary Search).

Mistakes that cost an interview

Operator precedence. In C++, Java, JavaScript, TypeScript and C#, == binds tighter than &, so n & 1 == 0 means n & (1 == 0). Asking whether 4 is even:

n = 4
print(n & 1 == 0)                     # is n even?

# True
public class Main {
    public static void main(String[] args) {
        int n = 4;
        System.out.println(n & 1 == 0);    // is n even?
    }
}

// won't compile: Main.java:4: error: bad operand types for binary operator '&'
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 4;
    cout << (n & 1 == 0) << "\n";         // is n even?
}

// 0
const n = 4;
console.log(n & 1 == 0);              // is n even?

// 0
const n: number = 4;
console.log(n & 1 == 0);              // is n even?

// won't compile: Main.ts(2,17): error TS2363: The right-hand side of an arithmetic operation must be of type 'any', 'number', 'bigint' or an enum type.
using System;

class Program {
    static void Main() {
        int n = 4;
        Console.WriteLine(n & 1 == 0);    // is n even?
    }
}

// won't compile: Main.cs(6,27): error CS0019: Operator '&' cannot be applied to operands of type 'int' and 'bool'
package main

import "fmt"

func main() {
	n := 4
	fmt.Println(n&1 == 0) // is n even?
}

// true

Python and Go read it as (n & 1) == 0; Java, TypeScript and C# refuse to compile it; C++ and JavaScript compute n & 0 and print 0, which is false, every time. Write the parentheses.

An odd check with %. x % 2 == 1 misses negative odd numbers wherever % keeps the sign. x & 1 is 1 for every odd x, negative ones included, in all seven.

Shifting by 32 or more. Java, JavaScript, TypeScript and C# use only the low 5 bits of the count, so 1 << 32 is 1 << 0. C++ doesn't define it. Python and Go just make a bigger number. One line of each, run:

s = 32
print(-7 % 2, 1 << s, -7 >> 1, -7 // 2, -7 & 1)

# 1 4294967296 -4 -4 1
public class Main {
    public static void main(String[] args) {
        int s = 32;
        System.out.println((-7 % 2) + " " + (1 << s) + " " + (-7 >> 1) + " " + (-7 / 2) + " " + (-7 & 1));
    }
}

// -1 1 -4 -3 1
#include <bits/stdc++.h>
using namespace std;

int main() {
    int s = 32;
    cout << (-7 % 2) << " " << (1 << s) << " " << (-7 >> 1) << " " << (-7 / 2) << " " << (-7 & 1) << "\n";
}

// -1 2106038464 -4 -3 1
const s = 32;
console.log(-7 % 2, 1 << s, -7 >> 1, Math.trunc(-7 / 2), -7 & 1);

// -1 1 -4 -3 1
const s: number = 32;
console.log(-7 % 2, 1 << s, -7 >> 1, Math.trunc(-7 / 2), -7 & 1);

// -1 1 -4 -3 1
using System;

class Program {
    static void Main() {
        int s = 32;
        Console.WriteLine($"{-7 % 2} {1 << s} {-7 >> 1} {-7 / 2} {-7 & 1}");
    }
}

// -1 1 -4 -3 1
package main

import "fmt"

func main() {
	s := uint(32)
	fmt.Println(-7%2, 1<<s, -7>>1, -7/2, -7&1)
}

// -1 4294967296 -4 -3 1
Languagen & 1 == 0, n = 4-7 % 21 << s, s = 32
PythonTrue14,294,967,296
Javawon't compile−11
C++0−1undefined
JavaScript0−11
TypeScriptwon't compile−11
C#won't compile−11
Gotrue−14,294,967,296

C++ printed 2,106,038,464 on one run, −785,934,144 on the next: undefined behaviour means whatever was in the register. The third and fourth numbers on each line are −7 >> 1 and −7 / 2. The shift rounds down to −4 everywhere; the division rounds toward 0, giving −3, except in Python, whose // rounds down too. A right shift is a division only for numbers that aren't negative. The last one, −7 & 1, is 1 in all seven.

1 << 31 when you mean 2³¹. In a 32-bit int it's the sign bit, −2,147,483,648. Shift a 64-bit one: 1L << 31 in Java and C#, 1LL << 31 in C++ printed 2,147,483,648.

Python's bin of a negative number. bin(-5) printed -0b101, a minus sign and 5's bits, not two's complement. Mask first: -5 & 0xFFFFFFFF is 4,294,967,291, whose bits are −5's 32.

Check yourself

Quiz

1 / 6

Multiple choice

In Java, what is -1 >> 1?

Practice

In this section, easy to hard:

  • Bitwise Operations Overview and Check K-th Bit: the masks above.
  • Power of Two: one set bit, and positive.
  • Counting Set Bits: n & (n − 1) until 0, or the built-in.
  • Toggle Rightmost Unset Bit: n | (n + 1).
  • Minimum Bit Flips to Convert Number: the 1s of start ^ goal.
  • Reverse Bits: 32 times, last bit of n onto the result.
  • Counting Bits: ones[i >> 1] + (i & 1).
  • Divisibility by 3 Check: 2 is one less than 3, so n is a multiple of 3 exactly when its 1s at even positions minus its 1s at odd positions is.

Next: XOR Tricks, where pairs cancel and the one left over is the answer.