Bitwise Operations Flashcards
What is the result of x & (x - 1)?
Clears the lowest set bit.
How do you check if a number is a power of 2 using bitwise operations?
n & (n - 1) == 0 for n > 0.
How do you swap two numbers using XOR?
a = a ^ b; b = a ^ b; a = a ^ b;
How do you find the single non-duplicate number in an array using XOR?
XOR all numbers; duplicates cancel out.
What is the purpose of a bitmask?
Representing subsets, toggling bits.
How do you find common bits? Or how do you return 1 if both bits are 1?
& AND operation.
How do you find the bitwise & of a range? Why does this work?
Shift both numbers right until they are equal, counting shifts. Then shift the result left. This works because numbers sharing a common prefix will retain it, while differing prefixes result in all 0
How do you accumulate bits that have appeared twice? Or compare two bits and return 1 if either is 1?
|OR operation.
How do you toggle bits (exclusive or)? Or remove duplicates?
^ XOR operation.
How do you invert all bits?
~ NOT operation. Flips all bits, and due to two’s complement, ~x is equivalent to -(x+1).
How do you shift bits to the left?
Left shift («), effectively multiplying by 2 for each shift.
How can you use bitwise operators to find a single digit in an array with others appearing three times?
Use ones, twos, and threes variables to track bit appearances.
How do you check if a number is odd or even using bitwise operations?
If n & 1 == 0, then n is even
If n & 1 == 1, then n is odd
