Bit Manipulation from Scratch: AND, OR, XOR, Shifts & Tricks (Java)

Every number in this array appears twice. Except one. Find it.

Most people reach for a HashMap. Count everything, then look for the count of one. That works, but it uses O of n extra memory.

Now watch this. Take every number, and XOR them all together. The pairs cancel out, and the one that's left is your answer. One loop. No extra memory. That's bit manipulation.

Welcome back to Compiled Canvas. This is Episode Six of our DSA series. In Episode Five, we covered the math you need for DSA. Today, we go one level deeper, to the bits inside every number.

Here's the plan. How numbers are stored in binary. The four operators: AND, OR, XOR and NOT. How negative numbers really work. Left and right shifts. How to check, set, clear and toggle any bit. The classic tricks, like checking for a power of two. The magic of XOR. Generating every subset with a bitmask. The Java traps that break bit code. A cheat sheet. And a quiz at the end.

Let's go.

First, binary. Your computer stores every number as bits, ones and zeros.

In normal numbers, each place is worth ten times the one to its right. Ones, tens, hundreds. In binary, each place is worth two times. One, two, four, eight, sixteen, and so on.

Take thirteen. That's eight, plus four, plus one. So in binary, it's one, one, zero, one. The eight is on, the four is on, the two is off, and the one is on.

To read a binary number, just add up the places that are on. One zero one zero is eight plus two, which is ten.

In Java, an int has thirty-two bits, and a long has sixty-four. We number the bits from the right, starting at zero. So bit zero is the ones place, bit one is the twos place, and bit three is the eights place.

And to see the bits of any number, use Integer dot toBinaryString. It's perfect for debugging bit code.

Now, the four operators. Each one works on the bits, one column at a time.

AND, written with a single ampersand. A bit is one only if both bits are one. Twelve is one one zero zero. Ten is one zero one zero. Twelve AND ten keeps only the columns where both are on: one zero zero zero, which is eight. Think of AND as a filter. It keeps only what both numbers share.

OR, written with a single vertical bar. A bit is one if at least one of the bits is one. Twelve OR ten is one one one zero, which is fourteen. Think of OR as a switch that turns bits on.

XOR, written with a caret. A bit is one if the two bits are different. Twelve XOR ten is zero one one zero, which is six. Think of XOR as "one or the other, but not both".

And NOT, written with a tilde. It flips every bit. Every zero becomes one, and every one becomes zero.

One small warning. Don't mix these up with double ampersand and double bar. Those are for true and false conditions. The single ones work on bits.

So what does NOT five give you? Not what you'd expect. It gives minus six.

To understand why, you need to know how Java stores negative numbers. It's called two's complement. The leftmost bit is the sign bit. If it's zero, the number is positive. If it's one, the number is negative.

And here's the rule. To get minus x, flip all the bits of x, and add one. That's why NOT x is always minus x, minus one.

So minus one is thirty-two ones in a row. And the smallest int, minus two point one billion, is a one followed by thirty-one zeros.

Why does Java do it this way? Because with two's complement, adding and subtracting work exactly the same for positive and negative numbers. The computer doesn't need special rules for the sign.

Next, shifts. A left shift moves every bit to the left, and fills the right with zeros.

Shifting left by one doubles the number. Five is one zero one. Shift it left by one, and you get one zero one zero, which is ten. Shift left by k, and you multiply by two to the power k.

And one shifted left by k gives you a number with just bit k turned on. This is called a mask, and you'll use it in almost every bit trick.

A right shift moves the bits to the right. Shifting right by one halves the number, and rounds down. Twenty shifted right by one is ten. Twenty-one shifted right by one is also ten.

Java has two right shifts. The normal one, with two arrows, keeps the sign. So minus eight, shifted right by one, is minus four. The unsigned one, with three arrows, always fills with zeros, so a negative number becomes a big positive one.

And here's where you've seen this before: binary search. low plus high, unsigned shifted right by one, is a safe middle, because even if the sum overflows, the three-arrow shift reads it as an unsigned number. So the middle always comes out right.

Quick pause, before we go further. If you're finding this video valuable, hit subscribe to Compiled Canvas, and turn on the bell. It's free, it takes one second, and it helps me keep making this complete DSA series for you. Alright, back to it.

Now, the four moves you'll use on a single bit. All of them use a mask: one shifted left by i.

To check bit i, AND the number with the mask. If the result isn't zero, the bit is on. Or shift the number right by i, and AND it with one. You get exactly zero or one.

To set bit i, turn it on: OR the number with the mask.

To clear bit i, turn it off: AND the number with NOT mask. NOT mask has every bit on except bit i, so everything else stays the same.

And to toggle bit i, flip it: XOR the number with the mask. If it was on, it turns off. If it was off, it turns on.

All four are O of one. One operation each, no loops.

And here's why this matters. With these four moves, a single int can act like an array of thirty-two true or false values. That's how you'll track which letters you've seen, or which items you've picked, using almost no memory.

Next, the classic tricks that come up in interviews again and again.

Is a number odd? Check n AND one. If it's one, the last bit is on, so the number is odd. That's faster than modulo two, and it also works for negative numbers.

Here's the most famous one: n AND n minus one. Subtracting one flips the lowest bit that's on, and every zero below it. So n AND n minus one clears the lowest set bit.

That gives you the power of two check. A power of two has exactly one bit on. So if n is greater than zero, and n AND n minus one is zero, then n is a power of two. Sixteen is one zero zero zero zero. Fifteen is zero one one one one. AND them, and you get zero.

You can also use it to count the bits that are on. Keep doing n equals n AND n minus one, and count the steps until n becomes zero. Each step removes one bit. That's called Brian Kernighan's algorithm, and it runs once per set bit, not once per bit. And in Java, Integer dot bitCount does it for you.

And one more: n AND minus n keeps only the lowest set bit. Twelve AND minus twelve gives four.

Now, the magic of XOR. Three rules make it special.

A number XOR itself is zero. A number XOR zero is the number itself. And the order doesn't matter, so you can XOR in any order you like.

Put those together, and you get the hook of this video. In an array where every number appears twice except one, XOR everything. Every pair cancels to zero. Zero XOR the single number is the single number. That's O of n time, and O of one space.

The same idea finds a missing number. If an array holds every number from zero to n except one, XOR all the indices, and all the values. Every number that's there cancels out, and the missing one is left.

And you may see XOR used to swap two numbers without a temp variable. It works, but in real code, just use a temp. It's clearer, and it's just as fast.

Next, one of the most useful tricks of all: generating subsets with a bitmask.

Say you have three items: a, b and c. Every subset is a choice for each item: in, or out. That's exactly what a bit is. So a three-bit number can describe any subset.

Bit zero is a, bit one is b, and bit two is c. The mask five is one zero one in binary, so it means a and c. The mask seven is one one one, which means all three. And zero means the empty set.

So to list every subset, loop the mask from zero up to one shifted left by n, minus one. For each mask, check each bit, and take the items whose bits are on.

There are two to the n subsets, and each one takes n steps to read. So it's O of two to the n, times n. That's fine when n is up to about twenty. Beyond that, it's too slow.

Now, the Java traps that break bit code.

Trap one: precedence. In Java, double equals is evaluated before the single ampersand. So if you write n AND one double equals zero, without brackets, it won't even compile. Always put brackets around the bit operation: open bracket, n AND one, close bracket, double equals zero.

Trap two: shifting too far. In an int, Java only uses the last five bits of the shift amount. So one shifted left by thirty-two is not zero. It's one. And one shifted left by thirty-one is already negative, because it lands on the sign bit. When you need bit thirty-one or higher, use a long: write one L, shifted left by k.

Trap three: two arrows or three. On negative numbers, the normal right shift keeps the sign, and the unsigned one doesn't. If a loop shifts a negative number right with two arrows, waiting for it to reach zero, it never will. It gets stuck at minus one.

So, which trick do you use? Here's the cheat sheet. Pause and screenshot this.

If every number appears twice except one, XOR everything.

If you need to check, set, clear or toggle a bit, use a mask: one shifted left by i.

If the problem asks whether n is a power of two, check that n is positive, and n AND n minus one is zero.

If it asks you to count the set bits, use n AND n minus one in a loop, or Integer dot bitCount.

If you need every subset of a small set, loop a bitmask from zero to two to the n.

And if you need to multiply or divide by a power of two, shift.

Okay, quiz time. Three questions. Pause the video, work out each answer, and then hit play.

Question one. What is five XOR three?

Question two. Is the check n AND n minus one equals zero enough, on its own, to test for a power of two?

Question three. In Java, what is one shifted left by thirty-two, for an int?

Ready?

Question one: six. Five is one zero one. Three is zero one one. The bits that differ give one one zero, which is six.

Question two: no. For n equals zero, the check also gives zero, but zero is not a power of two. You need n greater than zero too.

Question three: one. Java only uses the last five bits of the shift amount, so shifting by thirty-two is the same as shifting by zero.

How many did you get right? Tell me in the comments: three out of three, two, or one.

Let's recap. Every number is stored as bits, and each place is worth twice the one to its right. AND filters, OR turns bits on, XOR flips the bits that differ, and NOT flips them all. Negative numbers use two's complement, so NOT x is minus x, minus one. A left shift multiplies by two, and a right shift divides by two. A mask of one shifted left by i lets you check, set, clear or toggle any bit, in O of one. n AND n minus one clears the lowest set bit, and XOR cancels out pairs.

Your homework. Solve Single Number and Counting Bits on LeetCode, using only bit operations. Then tell me in the comments: what is six AND three?

Next episode, we start Module One: arrays in depth. How arrays sit in memory, why indexing is O of one, and what every operation really costs.

And don't forget to subscribe to Compiled Canvas, so you don't miss anything new in tech and the job market. Keep coding, stay consistent, and I'll see you in the next one.