cf.completefrontend
BIT MANIPULATION · FOUNDATION

Bitwise operators

Read, set, clear, and flip single bits of a number with &, |, ^, ~, and shifts, keeping in mind that JavaScript does this on 32-bit integers.

Time O(1)Space O(1)10 practice problemsStep-through picture

The idea

Computers store whole numbers as bits, a row of 0s and 1s. 13 is 1101 in binary: 8 + 4 + 1. Each position is a bit, numbered from the right starting at 0, so bit 0 is worth 1, bit 1 is worth 2, bit 2 is worth 4, and so on.

Bitwise operators work on every bit position at once. a & b (AND) keeps a 1 only where both have a 1. a | b (OR) keeps a 1 where either has one. a ^ b (XOR) keeps a 1 where exactly one has a 1. ~a (NOT) flips every bit. a << k shifts the bits k places left, which multiplies by 2^k, and a >> k shifts right, which divides by 2^k and rounds down. With a mask like 1 << i, which has only bit i set, these let you test, set, clear, or flip bit i.

JavaScript has a twist. Numbers are normally 64-bit floats, but every bitwise operator first converts its inputs to 32-bit signed integers, works on those, and returns a 32-bit signed result. Bit 31 is the sign bit, so 1 << 31 is -2147483648, and anything above 2^32 loses its high bits. The unsigned right shift >>> is the one exception: it returns an unsigned 32-bit value, so x >>> 0 turns a negative result back into its unsigned value, from 0 to 4294967295.

An everyday example

A row of light switches

Picture a panel of light switches, each either on or off, labeled 0, 1, 2, and so on from the right. To check one switch, cover all the others with tape and see if any light is on. To turn one on, flip it up whatever it was. To turn one off, flip it down. To toggle it, flip it the other way. A mask is the tape stencil that leaves only the switch you care about uncovered.

How the example maps to the code
In the exampleIn the code
The stencil that uncovers only switch i1 << i
Checking if switch i is on(n >> i) & 1
Turning switch i onn | (1 << i)
Turning switch i offn & ~(1 << i)
Flipping switch in ^ (1 << i)

From the slow way to bitwise operators

  1. Start with the obvious way to read bit i: turn the number into text with n.toString(2), count i characters from the right, and compare with "1". To set the bit you'd edit the text and turn it back into a number. That's slow and clumsy, and for negative numbers toString(2) prints "-101100", not the bits the computer really stores.
  2. Bitwise operators skip the text. They treat a number as a row of 32 bits and work on every position at the same time, in one step. To aim at a single position, build a mask: 1 << i is a number with only bit i set, like 16 (10000) for i = 4.
  3. Each job then matches one operator. AND with a 0 bit forces 0 and AND with a 1 bit keeps what was there; OR with a 1 forces 1; XOR with a 1 flips. So n | mask sets bit i, n & ~mask clears it, and n ^ mask flips it, while every other bit is untouched. To read it, (n >> i) & 1 slides bit i down to position 0 and throws the rest away.
  4. Last comes JavaScript's rule: inputs are cut to 32-bit signed integers, negatives are stored in two's complement, and >>> 0 reads the same bits as an unsigned number. One more classic, n & -n, keeps only the lowest set bit. Put each of these on its own line and you get bitTools, the toolkit of bitwise operators.

How it works

  1. Build a mask for bit i: 1 << i has only bit i set.
  2. Test bit i: shift it down to position 0 and keep only that bit, (n >> i) & 1. The result is 1 or 0.
  3. Set bit i with n | mask, clear it with n & ~mask, and flip it with n ^ mask.
  4. Isolate the lowest set bit with n & -n. In two's complement, -n is ~n + 1, which shares only that bit with n.
  5. When a result may have bit 31 set, use >>> 0 to read it as an unsigned number.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function bitTools(n, i) {
  2. const isSet = (n >> i) & 1;
  3. const withBit = n | (1 << i);
  4. const withoutBit = n & ~(1 << i);
  5. const flipped = n ^ (1 << i);
  6. const lowestBit = n & -n;
  7. const unsigned = n >>> 0;
  8. return { isSet, withBit, withoutBit, flipped, lowestBit, unsigned };
  9. }

How fast it is

TimeO(1)
Extra memoryO(1)

Each operator works on all 32 bits at once in a single machine step.

  • Best caseO(1)

    Any input: each operator handles all 32 bits in one machine step.

  • Average caseO(1)

    The same six operations for every n and i.

  • Worst caseO(1)

    Still six operations, even for n = 2147483647 or i = 31. Converting the input to 32 bits first is also a fixed amount of work.

Common mistakes

  • Forgetting that 1 << 31 is negative in JavaScript. Use >>> 0 or compare bits instead of comparing with > 0.
  • Using >> on a value that might be negative and expecting zeros to come in from the left. >> copies the sign bit; >>> brings in zeros.
  • Using bitwise operators on numbers above 2^32, such as timestamps in milliseconds. The high bits are silently lost.
  • Writing n & 1 === 0. === runs before &, so this is n & (1 === 0). Add brackets: (n & 1) === 0.

When to use it

Look for these clues in a problem:

  • The problem talks about binary, bits, flags, masks, or powers of two.
  • Values are small sets (up to 32 items) that could each be on or off.
  • The statement mentions 32-bit integers, overflow, or unsigned values.
  • You need a trick like "is this a power of two" or "lowest set bit" in O(1).

Check yourself

Answer each one in your head first, then open it.

Why is -44 >> 4 equal to -3 and not a large positive number?

>> copies the sign bit into the places it opens on the left, so the result stays negative. -44 >>> 4 brings in zeros instead and gives 268435453.

What is 44 & -44, and why?

4. The lowest 1 bit of 44 (101100) is worth 4, and it's the only bit that 44 and -44 have in common.

What is 1 << 32 in JavaScript?

1. Shift amounts use only their lowest 5 bits, so 32 becomes 0, and 1 << 0 is 1.

Why does n & 1 === 0 give the wrong answer?

=== runs before &, so it means n & (1 === 0), which is n & false, always 0. Write (n & 1) === 0.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 10 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

AND, OR, XOR, and NOT work on each bit position separately: bit k of the result depends only on bit k of the inputs. So you can check any of these lines one position at a time. The mask 1 << i has a 1 at position i and 0 everywhere else.

At every position other than i, the mask bit is 0, and x | 0 = x, x ^ 0 = x, and x & 1 = x (since ~mask has a 1 there). So those bits never change. At position i, x | 1 = 1 sets it, x & 0 = 0 clears it, and x ^ 1 flips it. That's exactly the set, clear, and flip jobs, with nothing else touched. For reading, n >> i moves bit i to position 0, and & 1 keeps only that position.

For n & -n, use the rule -n = ~n + 1. ~n flips every bit. Adding 1 turns the run of 1s at the bottom of ~n (the 0s at the bottom of n) back into 0s and carries into the first 0 of ~n, which is the lowest 1 of n. Above that bit, -n is still the flip of n, so they share nothing there. So the lowest set bit is the only one they share: for 44 (101100), that's 100, which is 4.

Going deeper

3 more ideas

How JavaScript stores the bits

Before any bitwise operator runs, JavaScript converts each input to a 32-bit signed integer. Negative numbers use two's complement: -1 is 32 ones, and -2 is 31 ones followed by a 0. So ~5 is -6, because flipping every bit of 5 gives the two's complement form of -6. Results come back as signed numbers, except for >>>, which treats the bits as unsigned.

Why n & (n - 1) and n & -n work

Subtracting 1 turns the lowest 1 bit into 0 and every 0 below it into 1. So n & (n - 1) clears the lowest set bit, and it is 0 exactly when n had a single 1 bit, which means n is a power of two. -n is ~n + 1: flipping every bit and adding 1 makes the lowest set bit of n the only bit that n and -n share.

Limits to remember

Shifts only use the lowest 5 bits of the shift amount, so 1 << 32 is 1, not 2^32. Numbers above 2^31 - 1 wrap around: 2 ** 31 | 0 is -2147483648. For values beyond 32 bits, use BigInt, which has its own bitwise operators without this limit, such as 1n << 40n.

Work it by hand

Every step in a table, with why

Run bitTools with i = 4 on 44 and on -44, side by side. Bit 4 is off in one and on in the other.

bitTools(44, 4) and bitTools(-44, 4)

StepLinen = 44n = -44What happensWhy
1n as 32 bits00101100…11010100the stored bits44 is 32 + 8 + 4. -44 is stored in two's complement: flip every bit of 44, then add 1. Only the last 8 of its 32 bits are shown; the rest are all 1.
2mask 1 << 416 (00010000)16 (00010000)only bit 4 is setThe mask is the same for both numbers.
3isSet = (n >> 4) & 12 & 1 = 0-3 & 1 = 1read bit 444 >> 4 is 2 (10), whose last bit is 0. -44 >> 4 is -3, because >> copies the sign bit in from the left, and its last bit is 1.
4withBit = n | mask60 (00111100)-44 (unchanged)set bit 4For 44 the bit turns on, adding 16. For -44 it was already on, so OR changes nothing.
5withoutBit = n & ~mask44 (unchanged)-60 (…11000100)clear bit 4~16 has every bit set except bit 4. ANDing with it clears bit 4 and keeps the rest.
6flipped = n ^ mask60-60flip bit 4XOR flips the bit either way: on for 44, off for -44.
7lowestBit = n & -n4 (00000100)4 (00000100)lowest set bit44 and -44 share exactly one bit: the lowest 1 of 44, worth 4.
8unsigned = n >>> 0444294967252read as unsignedFor -44, the same 32 bits read without a sign bit give 2^32 - 44 = 4294967252.

For 44 the result is { isSet: 0, withBit: 60, withoutBit: 44, flipped: 60, lowestBit: 4, unsigned: 44 }. For -44 it is { isSet: 1, withBit: -44, withoutBit: -60, flipped: -60, lowestBit: 4, unsigned: 4294967252 }. Every line is one operation, so there's no loop to end.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bitwise operatorsO(1)O(1)Reading or changing individual bits of values that fit in 32 bits: flags, masks, packed colors.
Binary text with toString(2)O(w)O(w)Only for showing bits to a person while debugging. Use (n >>> 0).toString(2) so negatives show their real bits.
An array of booleansO(1)O(n)More than 31 on/off values, or when readable code matters more than compact storage.
BigInt bitwise operatorsO(n)O(n)Values wider than 32 bits, such as 64-bit IDs. Each operation costs more as the number grows.

Extra memory: O(1): six numbers in the returned object.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Bitwise operators and the other approaches, on a scale where each line up is 10 times more steps.
  • Bitwise operators, An array of booleans O(1)
  • Binary text with toString(2), BigInt bitwise operators O(w)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Bitwise operators111
Binary text with toString(2)101,0001 million
An array of booleans111
BigInt bitwise operators101,0001 million

Inputs that need care

6 tricky inputs
Bit 31: bitTools(5, 31)
1 << 31 is -2147483648, so withBit comes out as -2147483643, a negative number. Read it with >>> 0 to get 2147483653, and never test bit 31 with > 0.
A shift of 32 or more: bitTools(5, 32)
Shifts only use the lowest 5 bits of the amount, so i = 32 acts like i = 0: isSet is 1 and withoutBit is 4. Check that i is from 0 to 31.
A number above 2^32: bitTools(2 ** 32 + 6, 1)
The high bits are dropped before any operator runs, so it behaves exactly like n = 6. Timestamps in milliseconds are this large; use BigInt for them.
n = 0
lowestBit is 0, which is how you know there is no set bit at all. isSet is 0 for every i.
The smallest 32-bit number: -2147483648
-n doesn't fit in 32 bits and wraps back to itself, so lowestBit is -2147483648, and unsigned is 2147483648. It's the one value whose negative is itself.
A decimal: bitTools(5.7, 0)
Bitwise operators cut off the fraction first, so it behaves like n = 5. That's why x | 0 is sometimes used to round toward zero, but only for values that fit in 32 bits.

Variations and follow-ups

Twists interviewers add

Packing several values into one number

A color like 0xff8800 packs red, green, and blue into 8 bits each. Read green with (color >> 8) & 255, which gives 136. Build it with (r << 16) | (g << 8) | b. Reading a field is shift, then mask.

Power-of-two test

n > 0 && (n & (n - 1)) === 0 is true only when n has a single 1 bit. Subtracting 1 clears that bit and sets the ones below it, so the AND is 0. It's used to check sizes for buffers and textures.

BigInt bits

BigInt has its own &, |, ^, ~, <<, and >> with no 32-bit limit, so 1n << 40n is exact. There's no >>>: 5n >>> 0n throws a TypeError, because BigInt values have no fixed width to be unsigned in.

Built-in helpers

Math.clz32(x) counts the leading zero bits of x as a 32-bit number, so 31 - Math.clz32(x) is the position of its highest set bit. Uint32Array stores values as unsigned 32-bit numbers, which avoids the sign surprise.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "without using +", "check if a number is a power of two", "toggle the state", "the lowest set bit", or a hint that values fit in 32 bits.
  • Explain each operation as "build a mask with only bit i, then AND to read or clear, OR to set, XOR to flip". Saying the mask first makes every line easy to follow.
  • Test a negative number, bit 0, and bit 31. Bit 31 is where JavaScript's signed results surprise people, and >> versus >>> behaves differently there.
  • Expect "why does n & -n give the lowest set bit?". Answer with -n = ~n + 1: the + 1 carries up to exactly the lowest 1 of n, and above it -n and n disagree on every bit.

Where frontend code uses it

The same idea in real UI code
  • WebGL takes bit masks as arguments: gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT) clears two buffers in one call.
  • x | 0 is an old trick to cut a number to a 32-bit integer, and you'll see it in minified code and in asm.js-style code. Math.trunc is clearer for normal use.
  • Canvas pixel data is often read through a Uint32Array view of an ImageData buffer, where each pixel's four color bytes are packed into one 32-bit number and pulled apart with shifts and & 0xff.

Related algorithms