Bit Manipulation
Computers store numbers as rows of 0s and 1s. Working directly on those bits (AND, OR, XOR, shifts) gives tricks that are fast and use no extra memory — such as XOR cancelling pairs of equal numbers.
After this topic: You can read and write the XOR, AND, shift and mask idioms and explain why each one works.
Do these first: 1-D Dynamic Programming
Step 1 · Read the lesson
XOR tricks, bit counting, in-place matrix moves, fast exponentiation and digit-by-digit arithmetic.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
- 1.Single NumberEasy
What is x XOR x? What is x XOR 0?
XOR all numbers: pairs cancel, the single number remains.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func singleNumber(nums []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// SingleNumber: every value appears twice except one. // x ^ x == 0 and x ^ 0 == x, so XOR-ing everything cancels the pairs. func SingleNumber(nums []int) int { result := 0 for _, n := range nums { result ^= n } return result } // MissingNumber: XOR every index and every value; only the missing number is left unpaired. func MissingNumber(nums []int) int { result := len(nums) for i, n := range nums { result ^= i ^ n } return result } - 2.Number of 1 BitsEasy
What does n & (n − 1) do to the lowest set bit?
Repeat n &= n−1 and count how many times until n is 0.
Target: O(number of set bits)
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func hammingWeight(n int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// HammingWeight: n & (n-1) clears the lowest set bit, so the loop runs once per 1-bit. func HammingWeight(n uint32) int { count := 0 for n != 0 { n &= n - 1 count++ } return count } // CountBits: bits of i = bits of i/2 (shift right) plus its last bit. func CountBits(n int) []int { bits := make([]int, n+1) for i := 1; i <= n; i++ { bits[i] = bits[i>>1] + i&1 } return bits } - 3.Counting BitsEasy
The bit count of i is related to the count of a smaller number.
bits[i] = bits[i >> 1] + (i & 1).
Target: O(n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func countBits(n int) []intTested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// HammingWeight: n & (n-1) clears the lowest set bit, so the loop runs once per 1-bit. func HammingWeight(n uint32) int { count := 0 for n != 0 { n &= n - 1 count++ } return count } // CountBits: bits of i = bits of i/2 (shift right) plus its last bit. func CountBits(n int) []int { bits := make([]int, n+1) for i := 1; i <= n; i++ { bits[i] = bits[i>>1] + i&1 } return bits } - 4.Reverse BitsEasy
Take the lowest bit of n and push it onto the result from the other side, 32 times.
For 32 iterations: result = (result << 1) | (n & 1); n >>= 1.
Target: O(32) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func reverseBits(n int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// ReverseBits: peel the lowest bit off n and push it onto the result from the right. func ReverseBits(n uint32) uint32 { var result uint32 for range 32 { result = result<<1 | n&1 n >>= 1 } return result } - 5.Missing NumberEasy
Numbers 0..n appear once except one. Which operation cancels equal values?
XOR all indices 0..n with all values (or sum formula n(n+1)/2 minus the array sum).
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func missingNumber(nums []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// SingleNumber: every value appears twice except one. // x ^ x == 0 and x ^ 0 == x, so XOR-ing everything cancels the pairs. func SingleNumber(nums []int) int { result := 0 for _, n := range nums { result ^= n } return result } // MissingNumber: XOR every index and every value; only the missing number is left unpaired. func MissingNumber(nums []int) int { result := len(nums) for i, n := range nums { result ^= i ^ n } return result } - 6.Sum of Two IntegersMedium
XOR adds without carrying. AND shows where carries happen.
Loop: sum = a ^ b; carry = (a & b) << 1; repeat until carry is 0 (mask to 32 bits for negative numbers).
Target: O(32) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func getSum(a int, b int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// GetSum: add without + or -. XOR is addition without carry, AND shows where the carries go. func GetSum(a, b int32) int32 { for b != 0 { carry := uint32(a&b) << 1 a ^= b b = int32(carry) } return a } - 7.Reverse IntegerMedium
Peel digits off with % 10 and push them on with ×10. Watch for overflow before it happens.
Loop digit = x % 10; x /= 10; check that rev·10 + digit stays within the 32-bit range before updating.
Target: O(log x) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func reverse(x int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// Reverse: reverse the digits of a 32-bit integer, or 0 if the result would overflow. // The overflow check happens BEFORE multiplying, because afterwards it is too late. func Reverse(x int) int { rev := 0 for x != 0 { digit := x % 10 x /= 10 if rev > math.MaxInt32/10 || (rev == math.MaxInt32/10 && digit > 7) { return 0 } if rev < math.MinInt32/10 || (rev == math.MinInt32/10 && digit < -8) { return 0 } rev = rev*10 + digit } return rev }