Skip to main content

Core Techniques

Bit Basics covers the model - what a bit is, what the operators do. This page is the toolbox built on top of it: setting, clearing, toggling, rotating, and the handful of identities that carry most single-integer interview problems. This is the page to actually memorize.

Single-bit ops​

Get a bit​

Every single-bit operation is the same two-step move: build the mask 1 << i, then combine it. Which operator you combine with decides what happens. Getting reads a column without writing it; setting and clearing write one, testing and toggling test and flip one.

x >> i slides bit i down to position 0, pushing everything below it off the end. & 1 then throws away everything still sitting above position 0, leaving just that one bit as a plain 0 or 1.

def get_bit(x: int, i: int) -> int:
return (x >> i) & 1
n =22
The registerThe number we are reading a bit out of.x0001011022
Slide bit i down to position 0Everything below bit i falls off the end.x >> i000000102
Mask off everything above itThe digit itself, always 0 or 1.(x >> i) & 100

Set a bit​

1 << i is a mask with a single 1 in column i and 0 everywhere else. OR-ing it into x can only turn that column on - every other column ORs against 0 and passes through unchanged, and a column that was already 1 stays 1.

def set_bit(x: int, i: int) -> int:
return x | (1 << i)
n =22
The registerThe number we are setting a bit in.x0001011022
Build the maskA single 1 in column i, 0 everywhere else.1 << i000010008
Set bit iOnly ever turns a column on.x | (1 << i)0001111030

Clear a bit​

~(1 << i) flips the mask: every column is 1 except column i, which is 0. AND-ing that into x forces column i to 0 (anything AND 0 is 0) while every other column ANDs against 1 and passes through unchanged.

def clear_bit(x: int, i: int) -> int:
return x & ~(1 << i)
n =22
The registerThe number we are clearing a bit in.x0001011022
Build the maskA single 1 in column i, 0 everywhere else.1 << i000010008
Invert itOnes everywhere except column i.~(1 << i)11110111247
Clear bit iOnly ever turns a column off.x & ~(1 << i)0001011022

Test a bit​

Same two-step move, the other two operators: AND without a shift asks whether a column is on, XOR flips it. Testing looks like getting, but stops one step earlier: x & (1 << i) keeps column i and zeroes the rest, without sliding anything down. The survivor is therefore the mask's value, not 1 - testing bit 3 yields 8, testing bit 7 yields 128. That is why the comparison is != 0 and never == 1. Reach for get_bit when you want the digit; reach for this when you only want the yes/no.

def test_bit(x: int, i: int) -> bool:
return x & (1 << i) != 0
n =22
The registerThe number we are testing a bit in.x0001011022
Build the maskA single 1 in column i, 0 everywhere else.1 << i000010008
Test bit iSurvives with its place value - 8 for bit 3, 128 for bit 7.x & (1 << i)000000000
The same test, as a yes/noCompare against 0, never against 1.x & (1 << i) != 0False

Toggle a bit​

XOR is the operator that asks "do these differ?" - so XOR-ing against the mask flips column i (it differs from 1 exactly when it was 0) and leaves every other column alone (anything XOR 0 is itself). Unlike set and clear, toggle is not idempotent: apply it twice and you are back where you started, which is what makes XOR its own inverse.

def toggle_bit(x: int, i: int) -> int:
return x ^ (1 << i)
n =22
The registerThe number we are toggling a bit in.x0001011022
Build the maskA single 1 in column i, 0 everywhere else.1 << i000010008
Toggle bit iFlips that one column, leaves the rest alone.x ^ (1 << i)0001111030
Toggle it againBack to x - toggle is its own undo, unlike set and clear.x ^ (1 << i) ^ (1 << i)0001011022

Odd or even​

Bit 0 is 1 for every odd number and 0 for every even one, so parity is just get_bit with i = 0 fixed - no % 2, no shift needed since the bit to test is already at position 0. It earns its own name because it is the one bit test you will write without thinking about masks at all.

def is_odd(n: int) -> bool:
return n & 1 == 1
 
def is_even(n: int) -> bool:
return n & 1 == 0

No mask to build and no i to choose - the only bit that matters is already at position 0. Scrub the register and watch the answer flip on every step:

n =22
The registerThe number we are checking the parity of.n0001011022
The parity bitBit 0, read straight off the bottom of the word.n & 100
n is oddThe same bit, as a yes/no.n & 1 == 1False
The % version, for comparisonSame answer for non-negative n; & 1 is just the shorter read.n % 200

Borrow & carry​

Clear all set bits​

Clearing the lowest set bit needs a trick (clearing the lowest set bit) because that bit's position is not known ahead of time. Clearing every set bit at once needs no trick at all: there is nothing left to locate. A value never disagrees with itself, so XOR-ing the register against itself cancels every column to 0 - equivalently, AND it against an all-zero mask.

def clear_all(x: int) -> int:
return x ^ x
n =172
The registerThe number we are clearing every bit of.x10101100172
XOR against itselfEvery column disagrees with itself nowhere, so all of them clear.x ^ x000000000
AND against zeroThe all-zero mask is the identity for "clear everything" - same result, no trick needed either way.x & 0000000000

Clear the lowest set bit​

Subtracting one turns the lowest 1 into 0 and every zero below it into 1. ANDing back against x keeps only the bits above, so exactly one set bit disappears per application. Loop until zero and the iteration count is the popcount: that is Brian Kernighan's algorithm, and it runs in number of set bits steps rather than width steps.

def popcount(n: int) -> int:
count = 0
while n:
n &= n - 1
count += 1
return count

Its most famous corollary: a power of two has exactly one set bit, so n > 0 and n & (n - 1) == 0.

n =172
The registerThe number we are clearing the lowest set bit of.x10101100172
The borrowLowest 1 turns off; every 0 below it turns on.x - 110101011171
Clear the lowest set bitExactly one set bit disappears per application.x & (x - 1)10101000168
x is a power of twoOne set bit left to clear, and clearing it empties the word.x > 0 and x & (x - 1) == 0False
Popcount, Kernighan-styleSteps taken to reach zero - never more than the number of set bits.while x: x &= x - 1; c += 14

Count set bits​

Counting the 1s in x - its popcount, or Hamming weight - is built into Python: x.bit_count() (3.10+) does it directly, no loop required. The Kernighan loop from clearing the lowest set bit is the manual version of the same idea: strip the lowest set bit one at a time and count the strips, which costs number of set bits iterations instead of width iterations. Reach for the loop only on Pythons without bit_count(), or when you need the count as a side effect of the stripping itself.

def popcount(x: int) -> int:
return x.bit_count()
 
def popcount_manual(x: int) -> int:
count = 0
while x:
x &= x - 1
count += 1
return count
n =172
The registerThe number whose set bits we are counting.x10101100172
Popcount, built-inPython 3.10+; no loop, no manual masking.x.bit_count()4
Popcount, Kernighan-styleSame answer, one strip per set bit.while x: x &= x - 1; c += 14

Adding 1: the mirror carry​

x - 1 is a borrow that runs right-to-left: it flips every trailing 0 to 1 until it hits the lowest 1, which it flips to 0 and stops there (clearing the lowest set bit). Adding 1 runs the exact mirror-image carry instead: it flips every trailing 1 to 0 until it hits the lowest 0, which it flips to 1 and stops there. So x + 1 sets the lowest clear bit and clears every bit below it - the opposite of x & (x - 1) clearing the lowest set bit and setting every bit below it.

n =172
The registerThe number we are adding 1 to.x10101100172
The carryLowest 0 turns on; every 1 below it turns off.x + 110101101173

Set the lowest clear bit​

Every number short of "all 1s" has a lowest clear bit somewhere in its width. x + 1's carry chain flips every trailing 1 to 0 and stops at that lowest 0, setting it to 1 (the mirror carry walks through why) - but that wipes out the trailing ones along the way, which is more than "just set one bit." ORing the carry result back against the original x restores those trailing ones, since x still has them as 1; the lowest clear bit survives the OR too, because it went from 0 in x to 1 in x + 1, and OR only ever turns bits on. Net effect: exactly one bit changes - the lowest clear bit flips on, everything else, trailing ones included, stays exactly as it was.

def set_lowest_clear_bit(x: int) -> int:
return x | (x + 1)
n =183
The registerThe number whose lowest clear bit we are setting.x10110111183
The carryLowest 0 turns on; every 1 below it turns off.x + 110111000184
Set the lowest clear bitThe trailing ones survive the OR; only the lowest clear bit changes.x | (x + 1)10111111191

Set all trailing zeros​

x - 1 sets every bit below the lowest set bit (clearing the lowest set bit) without touching the lowest set bit itself, which flips to 0. OR-ing that back against x restores the lowest set bit while keeping the newly-set bits below it, so the net effect is "leave everything above the lowest set bit alone, and turn on everything from the lowest set bit down to bit 0."

n =172
The registerThe number whose trailing zeros we are setting.x10101100172
The borrowLowest 1 turns off; every 0 below it turns on.x - 110101011171
Set all trailing zerosThe lowest set bit survives the OR; everything below it is now on too.x | (x - 1)10101111175

Clear all trailing ones​

x + 1 sets every bit below the lowest clear bit (the mirror carry) and flips the lowest clear bit itself to 1. ANDing that back against x restores every bit above the lowest clear bit while wiping out the bits below it, since those were the trailing 1s that x + 1 just turned to 0. Net effect: "leave everything above the lowest clear bit alone, and turn off everything from the lowest clear bit down to bit 0" - the exact mirror of setting all trailing zeros's x | (x - 1).

n =175
The registerThe number whose trailing ones we are clearing.x10101111175
The carryLowest 0 turns on; every 1 below it turns off.x + 110110000176
Clear all trailing onesThe lowest clear bit survives the AND; everything below it is now off too.x & (x + 1)10100000160

Isolate the lowest set bit​

x & -x isolate the lowest 1x10101100-x01010100x & -x00000100above bit 2 the two rows disagree in every columnx = 172 = 10101100, lowest set bit is bit 2

Because -x == ~x + 1, the carry chain stops at the lowest set bit, leaving every higher column inverted (so it cannot match) and every lower column zero. Only the lowest set bit agrees. Use it to grab the next element out of a bitmask, and (x & -x).bit_length() - 1 to get its index.

n =172
The registerThe number whose lowest set bit we are isolating.x10101100172
Two’s complement of xShown inside the 8-bit word.-x == ~x + 10101010084
Isolate the lowest set bitThe bit’s value, not its index - so it is 4, not 2.x & -x000001004
Its indexNo lowest set bit when x is 0, which is why this reads -1 there.(x & -x).bit_length() - 100102
Lowest set bit plus everything belowThe same bit, smeared downward - a trailing-zero mask.x ^ (x - 1)000001117

Structural & arithmetic tricks​

Powers of two, four, eight, sixteen​

Being a power of two is "exactly one set bit" (clearing the lowest set bit): n > 0 and n & (n - 1) == 0. Being a power of a bigger power of two - 4, 8, 16, ... - is the same one-bit test plus a constraint on which bit is set: 4's set bits sit at indices 0, 2, 4, ...; 8's at 0, 3, 6, ...; 16's at 0, 4, 8, .... Rather than compute that index with bit_length(), a constant mask with a 1 at exactly those positions answers "is the lone bit one of them?" with a single AND: 0b01010101...0101 (every 2nd bit) for four, 0b01001001...1001 (every 3rd bit) for eight, 0b00010001...0001 (every 4th bit) for sixteen - written as binary literals, the period is visible in the digits themselves.

def is_power_of_two(n: int) -> bool:
return n > 0 and n & (n - 1) == 0
 
def is_power_of_four(n: int) -> bool:
return is_power_of_two(n) and n & 0b01010101010101010101010101010101 != 0
 
def is_power_of_eight(n: int) -> bool:
return is_power_of_two(n) and n & 0b01001001001001001001001001001001 != 0
 
def is_power_of_sixteen(n: int) -> bool:
return is_power_of_two(n) and n & 0b00010001000100010001000100010001 != 0
n =64
The registerThe number we are testing.n000000000100000064
The borrowLowest 1 turns off; every 0 below it turns on.n - 1000000000011111163
n is a power of twoZero exactly when n has one set bit.n & (n - 1)00000000000000000
Mask for fourA 1 every 2nd bit.0b0101...0101010101010101010121845
n is a power of fourNon-zero only for 1, 4, 16, 64, ...n & mask_4000000000100000064
Mask for eightA 1 every 3rd bit.0b1001...1001100100100100100137449
n is a power of eightNon-zero only for 1, 8, 64, 512, ...n & mask_8000000000100000064
Mask for sixteenA 1 every 4th bit.0b0001...000100010001000100014369
n is a power of sixteenNon-zero only for 1, 16, 256, 4096, ...n & mask_1600000000000000000

n = 64 is a good register to scrub through: it is 2**6, so its lone set bit sits at index 6 - that's why it passes power-of-two, power-of-four, and power-of-eight (6 is a multiple of 2 and 3) but fails power-of-sixteen (6 is not a multiple of 4).

Reversing all the bits of a fixed-width integer​

To reverse all 32 bits of an integer, repeatedly split it into blocks and swap them: first the two 16-bit halves, then 8-bit blocks within each half, then 4-bit, 2-bit, and finally 1-bit blocks. Each step uses a mask to isolate the relevant bits and shifts them into their mirrored position, then ORs the two halves together. After five passes every bit has migrated to its mirror position - a fixed five operations instead of a 32-iteration bit-by-bit loop.

16-bit8-bit4-bit2-bit1-bit
All five passes of the 32-bit reversal: each row halves the block size and swaps every adjacent pair of blocks, until the last row swaps individual bits with their mirror.
class Solution:
def reverseBits(self, n):
n = ((n & 0b11111111111111111111111111111111) >> 16) | (
(n & 0b11111111111111111111111111111111) << 16
)
n = ((n & 0b11111111000000001111111100000000) >> 8) | (
(n & 0b00000000111111110000000011111111) << 8
)
n = ((n & 0b11110000111100001111000011110000) >> 4) | (
(n & 0b00001111000011110000111100001111) << 4
)
n = ((n & 0b11001100110011001100110011001100) >> 2) | (
(n & 0b00110011001100110011001100110011) << 2
)
n = ((n & 0b10101010101010101010101010101010) >> 1) | (
(n & 0b01010101010101010101010101010101) << 1
)
return n

Each later pass halves the block size (8, then 4, then 2, then 1 bit) and does the identical swap-and-shift within each half from the previous pass - by the last pass, every individual bit has traded places with its mirror.

The same idea on a single byte needs only three passes - swap 4-bit halves, then 2-bit pairs within each half, then adjacent single bits - since log2(8) = 3. Scrub the register below to see every pass update together:

def reverse_byte(n: int) -> int:
n = ((n & 0b11110000) >> 4) | ((n & 0b00001111) << 4)
n = ((n & 0b11001100) >> 2) | ((n & 0b00110011) << 2)
n = ((n & 0b10101010) >> 1) | ((n & 0b01010101) << 1)
return n
n =180
The registerThe byte we are mirroring.n10110100180
Swap 4-bit halvesThe top nibble and bottom nibble trade places.(n & 0b11110000) >> 4 | (n & 0b00001111) << 40100101175
Swap 2-bit pairsWithin each nibble, the two pairs trade places.(n & 0b11001100) >> 2 | (n & 0b00110011) << 20001111030
Swap adjacent bitsEvery bit trades with its neighbor - the byte is now fully mirrored.(n & 0b10101010) >> 1 | (n & 0b01010101) << 10010110145

Swapping two variables without a temp​

XOR has two useful properties: a value XORed with itself is 0, and a value XORed with 0 is unchanged. Chaining three XOR assignments swaps a and b in place, with no temporary variable:

def swap_nums(a, b):
a = a ^ b
b = b ^ a
a = a ^ b
return a, b
n =5
The first registerStarting value of a.a1015
The second registerStarting value of b.b0113
Combine both into aHolds combined info of both.a = a ^ b1106
Recover original a into bOriginal a, cancelled out of the combined value.b = b ^ a1015
Recover original b into aOriginal b, cancelled out - swap complete, no temp used.a = a ^ b0113
XOR swap fails if a and b are the same variable

arr[i], arr[i] = arr[i] ^ arr[i], ... zeroes the slot on the first line, because a value XORed with itself is always 0 - there is nothing left to swap with. This only bites when the two "variables" can alias the same storage (the same array index passed twice); plain distinct local variables are never a problem.

Add without +​

XOR gives the sum of two bits ignoring any carry (0^1=1, but 1^1=0 where a real carry would appear); AND finds exactly the columns where both bits were 1 - the columns a carry gets generated from. Shifting that left by one moves each carry into the column it affects, exactly like carrying a digit in long addition. Assigning both at once (a, b = a ^ b, (a & b) << 1) and repeating drives b toward 0, because each pass pushes any remaining carry one column further left, and a fixed-width number runs out of columns. When b finally hits 0, a holds the sum.

def add(a: int, b: int) -> int:
while b:
a, b = a ^ b, (a & b) << 1
return a
n =12
The first registerStarting value of a.a0000110012
The second registerStarting value of b.b0000101010
Sum without carryXOR adds ignoring any carry.a ^ b000001106
Where a carry occursAND finds the shared bits; the shift moves each into the next column.(a & b) << 10001000016
Second pass: new sumThe first sum and its carry combine again.(a^b) ^ ((a&b)<<1)0001011022
Second pass: new carry - zero, doneNo columns collide this time, so the loop stops - the sum above is final.((a^b) & ((a&b)<<1)) << 1000000000

Rotate left by k​

A shift throws bits away; a rotation wraps them around instead - the bits that fall off one end reappear at the other. Rotation only makes sense once you fix a width w (there is no "rotate" on Python's unbounded integers without deciding how many bits you are rotating within).

(n << k) slides every bit left by k, which is exactly what pushes the top k bits off the word. (n >> (w - k)) recovers those same top k bits at the bottom of the word instead (a plain right shift by the complementary distance). OR-ing the two together drops the wrapped bits back in where the shift emptied them out, then the final & ((1 << w) - 1) trims the result back down to w bits.

n =10110100180rotl(n, 3) =10100101165 - nothing is lostcarries a 1carries a 0compare to a plain shift: a rotation never zero-fills and never drops a bit
def rotate_left(n: int, k: int, w: int) -> int:
return ((n << k) | (n >> (w - k))) & ((1 << w) - 1)

That one line is four separate moves stacked together. Toggle a bit or scrub k below and watch all four terms move together - the two middle rows are drawn 16 bits wide because they genuinely overflow the word; the trim is what pulls them back in.

n =180
The registerThe number we are rotating.n10110100180
Slide left, losing the top kPast bit 7 is outside the word.n << k00000101101000001440
The same top k, re-enteringA plain right shift by the complementary distance.n >> (w - k)00000000000001015
MergedOR drops them into the gap the shift left.(n << k) | (n >> (w - k))00000101101001011445
Trimmed - rotate leftDeletes everything past bit 7.... & ((1 << w) - 1)10100101165

Scrub k to 0 or 8 and the result is n again: a rotation by the full width is the identity. Both ends still work here only because Python shifts by any distance - in C, n >> (w - k) at k = 0 shifts by the full width, which is undefined behaviour, so fixed-width code guards with k %= w first.

Rotate right by k​

Mirror image of rotate-left: (n >> k) slides every bit right by k, dropping the bottom k bits off the word. (n << (w - k)) recovers those same bottom k bits at the top of the word instead. OR-ing the two together and masking to w bits puts them back where the shift emptied them out.

n =10110100180rotr(n, 3) =10010110150 - nothing is lostcarries a 1carries a 0the bottom k bits wrap to the top instead of the top k wrapping to the bottom
def rotate_right(n: int, k: int, w: int) -> int:
return ((n >> k) | (n << (w - k))) & ((1 << w) - 1)

The same walkthrough, mirrored: the two shifts swapped, so the bottom k bits are the ones that leave and re-enter at the top.

n =180
The registerThe number we are rotating.n10110100180
Slide right, losing the bottom kBit 0 is outside the word.n >> k000000000001011022
The same bottom k, re-enteringA plain left shift by the complementary distance.n << (w - k)00010110100000005760
MergedOR drops them into the gap the shift left.(n >> k) | (n << (w - k))00010110100101105782
Trimmed - rotate rightDeletes everything past bit 7.... & ((1 << w) - 1)10010110150

Hardware and most systems languages expose this as a single instruction rather than a mask-and-shift idiom - x86 has ROL/ROR, and C compilers usually recognize the mask-and-shift pattern above and emit one anyway. Python's own int has no built-in rotate because it has no fixed width to rotate within; you always supply w yourself.

Bitmasks as sets​

Bitmasks: a whole set inside one integer​

If you have at most about 20 to 30 items, you do not need a set. Assign each item a bit position and the entire subset becomes a single integer, with set operations that are one machine instruction each.

jambit 3breadbit 2eggsbit 1milkbit 01010mask =0b1010 = 10 = the subset {jam, eggs}4 items = 16 possible subsets = the integers 0 through 15"try every subset" becomes: for mask in range(1 << 4)n items cost 2^n masks, which is why bitmask DP tops out around n = 20

The register below is the set m over n = 8 items, with i = 2 and a fixed partner set b = 0b00001111. Toggle a bit and every membership answer moves with it.

n =10
Empty set / full set of nThe two ends of the range every bitmask loop walks.0 / (1 << n) - 111111111255
Add item iIdempotent - adding twice is adding once.m |= 1 << i0000111014
Remove item iThe inverted mask spares every other column.m &= ~(1 << i)0000101010
Toggle item iThe only one of the three that is not idempotent.m ^= 1 << i0000111014
Contains item im >> i & 1False
Union / intersection with bShown here as the union.a | b / a & b0000111115
Difference m - ba & ~b000000000
Symmetric difference with ba ^ b000001015
m is a subset of ba & b == aTrue
Size of the setPython 3.10+.m.bit_count()00102
Complement within n itemsm ^ ((1 << n) - 1)11110101245

Two enumeration patterns are worth memorizing verbatim:

# every subset of n items, in 2**n steps
for mask in range(1 << n):
chosen = [items[i] for i in range(n) if mask >> i & 1]
 
# every member of one mask, in popcount steps
m = mask
while m:
low = m & -m # isolate
i = low.bit_length() - 1 # its index
m ^= low # remove it and continue
 
# every SUBMASK of a mask (all 3**n over all masks, not 4**n)
sub = mask
while sub:
... # use sub
sub = (sub - 1) & mask
# note: the empty submask 0 is never visited by the loop above
When a bitmask is the right call

Small fixed universe (letters of the alphabet, up to ~20 cities, a set of visited states), and you need set operations to be free. Count the Number of Consistent Strings maps letters to bits; Palindrome Permutation uses one integer as 26 parity counters. If the universe is large or unbounded, use a real set.

Reference​

The cheatsheet​

Everything above, compressed. This is the page to reread before an interview.

Test
Is n oddFaster to read than n % 2.n & 1
Is bit i setn >> i & 1
Is n a power of twoExactly one set bit.n > 0 and n & (n - 1) == 0
Is n all ones (2**k - 1)n & (n + 1) == 0
Do x and y differ in signThe sign bit is the only one that matters.(x ^ y) < 0
No two adjacent set bitsUsed by Gray-code and tiling problems.n & (n >> 1) == 0
Isolate
Lowest set bitReturns the bit value, not its index.n & -n
Index of lowest set bit(n & -n).bit_length() - 1
Index of highest set bitAlso floor(log2(n)) for n > 0.n.bit_length() - 1
Lowest set bit plus all belown ^ (n - 1)
Low k bitsn & ((1 << k) - 1)
Clear and set
Clear the lowest set bitBrian Kernighan’s step.n & (n - 1)
Clear all trailing onesn & (n + 1)
Set the lowest clear bitn | (n + 1)
Set all trailing zerosn | (n - 1)
Flip bits within n’s widthNot ~n - Python’s ~ sign-extends forever. bit_length() is 0 for n == 0, so grow the mask with a loop there instead.n ^ ((1 << n.bit_length()) - 1)
Count and measure
PopcountPython 3.10+; else bin(n).count("1").n.bit_count()
Popcount by handRuns in popcount steps, not 32.while n: n &= n - 1; c += 1
Hamming distanceXOR first, then count.(x ^ y).bit_count()
Number of bits in n0 for n == 0.n.bit_length()
Arithmetic
Multiply / divide by 2**kRight shift floors.n << k / n >> k
Next power of two >= nFor n > 1.1 << (n - 1).bit_length()
Round down to a power of twoFor n > 0.1 << (n.bit_length() - 1)
-nTwo’s complement, by definition.~n + 1
~nThe Python identity people forget.-n - 1
Add without +XOR is sum-without-carry, (a & b) << 1 is the carry; repeat until no carry remains.while b: a, b = a ^ b, (a & b) << 1
Absolute value, branchless32-bit. n >> 31 is all-1s for negative n, all-0s otherwise - it is a sign-selected mask, not a comparison.(n ^ (n >> 31)) - (n >> 31)
Min without comparisonThe real branchless version replaces a < b with a sign-bit trick too; shown here for the shape - a plain min(a, b) is clearer in Python.b ^ ((a ^ b) & -(a < b))
Combine
Swap without a tempFails if a and b are the same variable.a ^= b; b ^= a; a ^= b
Value appearing once, rest twicePairs cancel.reduce(xor, nums)
Gray code of nConsecutive codes differ by one bit.n ^ (n >> 1)
Encode / decode with one opXOR is its own inverse.enc = a ^ k, a = enc ^ k
Write a value in
Write bit i to vClear first, then drop the new value in.x & ~(1 << i) | (v << i)
Write bits [lo, hi) to vSame clear-then-drop-in idea as writing one bit, just with a wider mask.x & ~(((1 << (hi - lo)) - 1) << lo) | (v << lo)
A run of bits at once
Take the low k bitsSame as x % 2**k for non-negative x.x & ((1 << k) - 1)
Read bits [lo, hi)Generalizes "take the low k bits" to any window - shift the window to the origin first, then mask its width.(x >> lo) & ((1 << (hi - lo)) - 1)

Where to go next​

0%0 of 30 pages studied