PHASE 1Beginner ~29 min· topic 9 of 14

Topic 1.9

Bitwise and Shift Operators

In one line

Bitwise operators (&, |, ^, ~) work on the individual bits of integers, and shift operators (<<, >>, >>>) slide those bits left or right. They're how Java packs many flags into one number, tests for odd numbers and powers of two in one step, and how HashMap picks a bucket.

Think of it like this

A panel of light switches in a row, each either on (1) or off (0). An int is a panel of 32 switches. AND keeps a light on only if it's on in both panels, OR turns it on if it's on in either, XOR turns it on where the panels differ, NOT flips every switch, and a shift slides the whole pattern along the row.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Bitwise: Working on each bit of a number separately, position by position.
AND (&): A bit is 1 in the result only if it is 1 in both inputs.
OR (|): A bit is 1 in the result if it is 1 in either input.
XOR (^): Exclusive or: a bit is 1 in the result if the two inputs differ at that position.
Shift: Moving all the bits of a number left or right by some number of places.
Mask: A number whose 1-bits pick out the positions you care about, used with &, | or ^.
Flag: A single bit that records yes/no for one option.
Set bit: A bit whose value is 1.
Hexadecimal: Base-16 notation, written with 0x. Each hex digit stands for exactly 4 bits: 0xFF is 11111111.

Step by step

01AND, OR, XOR column by column

Line the two numbers up in binary and compare each column. With 12 (1100) and 10 (1010): AND keeps columns where both are 1 → 1000 = 8. OR keeps columns where either is 1 → 1110 = 14. XOR keeps columns where they differ → 0110 = 6.

These are the same truth tables as the boolean &&, ||, ^ in Topic 1.8, applied to 32 columns at once.

AND, OR, XOR column by columndiagram

Rendering diagram…

02NOT and the -x - 1 rule

~12 flips all 32 bits of 0000…1100 to 1111…0011. In two's complement that's -13. In general ~x == -x - 1, which also explains why negation is ~x + 1.

03Left shift multiplies by powers of two

x << n moves every bit n places left and fills the right with zeros, which multiplies by 2ⁿ: 3 << 4 is 48. Bits pushed past position 31 are lost, so 1 << 31 is Integer.MIN_VALUE (the sign bit) and larger shifts overflow.

1 << k is the standard way to build a number with only bit k set, the building block of every mask.

04Two right shifts: >> and >>>

>> (signed) fills the left with copies of the sign bit. Positive numbers get zeros, negative numbers get ones, so the sign is kept and the result is division by 2ⁿ rounded down (toward negative infinity): -7 >> 1 is -4, while -7 / 2 is -3.

>>> (unsigned) always fills with zeros. For negative numbers the result is a big positive number: -16 >>> 28 keeps the top four 1-bits and gives 15. It's how you treat an int as 32 unsigned bits, and why (low + high) >>> 1 fixes the binary search midpoint (Topic 1.3).

Two right shifts: >> and >>>diagram

Rendering diagram…

05Shift distances wrap around

The JLS says only the low 5 bits of the shift distance are used for int (distance & 31) and the low 6 bits for long (distance & 63). So 1 << 32 is 1 << 0 = 1, and 1 << 40 is 1 << 8 = 256. Negative distances wrap too: 1 << -1 is 1 << 31.

This matches what x86 and ARM shift instructions do, so it's fast, but it means long mask = 1 << 40; silently produces 256. The literal 1 is an int; write 1L << 40.

06Flags in a single int

Give each option its own bit: READ = 1 << 0, WRITE = 1 << 1, EXECUTE = 1 << 2. A set of permissions is then one int: READ | WRITE is 011 = 3.

Test: (perms & WRITE) != 0. Add: perms |= EXECUTE. Remove: perms &= ~WRITE (AND with everything except that bit). Toggle: perms ^= READ.

Note the brackets in (perms & WRITE) != 0: != has higher precedence than &, so without them Java tries perms & (WRITE != 0), which doesn't compile.

07Bit tricks you'll meet in interviews and the JDK

Odd/even: (n & 1) is 1 for odd numbers, including negatives. Power of two: n > 0 && (n & (n - 1)) == 0, because a power of two has exactly one set bit, and subtracting 1 turns it into all ones below it. Lowest set bit: n & -n.

XOR pairs cancel: a ^ a == 0 and a ^ 0 == a, so XOR-ing all values where every value appears twice except one leaves that one. The DSA course (/dsa) has a bit manipulation module built on these.

HashMap: table sizes are powers of two so that hash & (n - 1) can replace the slower hash % n when picking a bucket. Topic 9.4 shows this in the real source code.

Try it yourself

1
Predict before you print
Work out 6 & 3, 6 | 3, 6 ^ 3 and ~6 on paper (6 is 110, 3 is 011), then add them to the first example. (Answers: 2, 7, 5, -7.)
2
Add a permission
Add static final int DELETE = 1 << 3; to the flags example, grant it, and print the binary. Then test whether the user has both READ and DELETE with (perms & (READ | DELETE)) == (READ | DELETE).
3
Find the unpaired number
XOR together 3, 9, 5, 9, 3 and print the result. Every value that appears twice cancels out, leaving 5.

Code & diagrams

The four bitwise operators and two shifts New tab

`toBinaryString` drops leading zeros, so 0110 prints as 110.

Expected output

a      = 1100
b      = 1010
a & b  = 1000 = 8
a | b  = 1110 = 14
a ^ b  = 110 = 6
~a     = -13  (always -a - 1)
a << 2 = 48
a >> 2 = 3

Shifts with negative numbers and big distances New tab

Expected output

n          = 11111111111111111111111111110000
n >> 2     = -4
n >>> 2    = 1073741820
n >>> 28   = 15
-7 >> 1    = -4   but -7 / 2 = -3
1 << 31    = -2147483648
1 << 32    = 1
1L << 32   = 4294967296
raw        = -16
raw & 0xFF = 240

Permission flags in one int New tab

Expected output

perms          = 11
can write?       true
can execute?     false
grant execute  = 111
revoke write   = 101
toggle read    = 100

Bit tricks: odd, power of two, lowest bit, XOR New tab

Expected output

1: odd=true pow2=true bits=1 lowest=1
6: odd=false pow2=false bits=2 lowest=2
8: odd=false pow2=true bits=1 lowest=8
12: odd=false pow2=false bits=2 lowest=4
64: odd=false pow2=true bits=1 lowest=64
swapped: x=9 y=5
unpaired in 4,7,4: 7

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Shift an int by 40

Write long mask = 1 << 40; hoping for 2⁴⁰.

terminal

$ javac Main.java

java Main

── what you'll see ──

256

Break #2

Forget brackets around a mask test

Write if (flags & WRITE != 0).

terminal

$ javac Main.java

── what you'll see ──

Main.java:5: error: bad operand types for binary operator '&'

if (flags & WRITE != 0) {

first type: int

second type: boolean

1 error

Break #3

Put 0xFF into a byte

Write byte mask = 0xFF;.

terminal

$ javac Main.java

── what you'll see ──

Main.java:3: error: incompatible types: possible lossy conversion from int to byte

byte mask = 0xFF;

1 error

Myth vs fact

Myth

>> and >>> are the same.

Fact

They differ for negative numbers: >> copies the sign bit (stays negative), >>> fills with zeros (becomes positive).

Myth

Shifting by 32 or more clears an int to zero.

Fact

The distance is taken modulo 32 for int (64 for long), so x << 32 is x.

Myth

Bit tricks always make code faster.

Fact

The JIT already turns x * 8 into a shift and x % 8 (for provably non-negative x) into a mask. Use bit operations for meaning (flags, masks), and measure before using them for speed.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Integer.bitCount, numberOfLeadingZeros, numberOfTrailingZeros, Long.bitCount and friends are HotSpot intrinsics that compile to single instructions (popcnt, lzcnt, tzcnt) on CPUs that support them.
▸
Java 19 added Integer.compress and Integer.expand (and Long versions), bit gather/scatter operations that map to the BMI2 pext/pdep instructions on x86.
▸
HashMap.hash() computes h ^ (h >>> 16) before masking with n - 1, so the high bits of a poor hashCode still influence the bucket index. That one line is why power-of-two tables are safe in practice (Topic 9.4).
▸
java.util.BitSet stores flags in a long[] (64 per word) and grows as needed, and EnumSet uses a single long bit vector for enums with up to 64 constants, giving readable code with bitwise-level performance.

Remember this

1
& (AND), | (OR), ^ (XOR) compare two integers bit by bit, position by position. ~ (NOT) flips every bit; because of two's complement (Topic 1.3), ~x always equals -x - 1.
2
<< shifts left, filling with zeros: each step doubles the number (5 << 3 is 40) until bits fall off the top. >> is an arithmetic right shift that copies the sign bit in, so it halves and keeps negatives negative (-16 >> 2 is -4). >>> is a logical right shift that fills with zeros, so a negative number becomes a large positive one.
3
The shift distance is masked: for int only the low 5 bits of the distance are used (0–31), for long the low 6 (0–63). So 1 << 32 is 1, not 0, and 1 << 40 is 256. To shift beyond 31, shift a long: 1L << 40.
4
Classic tricks: (n & 1) == 0 tests even; n & (n - 1) clears the lowest set bit, so n > 0 && (n & (n - 1)) == 0 tests for a power of two; n & -n isolates the lowest set bit; x ^ x is 0, so XOR-ing a list finds the one value without a pair.
5
Flags: give each option one bit (READ = 1, WRITE = 2, EXEC = 4), combine with |, test with (flags & WRITE) != 0, clear with flags &= ~WRITE, toggle with flags ^= WRITE. Unix file permissions and many network protocols are built this way; in Java code, EnumSet is the readable alternative.
6
Bytes are signed, so a raw byte like 0xF0 reads as -16. b & 0xFF gives its unsigned value 0–255, a pattern you'll use for files, network data and hashing. Helpers such as Integer.toBinaryString, Integer.bitCount, Integer.highestOneBit and Integer.numberOfTrailingZeros do common jobs in one call (most compile to a single CPU instruction).

Explain it without notes

Explain the difference between >> and >>> with a negative number.

Why is n > 0 && (n & (n - 1)) == 0 a test for powers of two?

How do you set, clear, toggle and test one flag bit in an int?

Why does 1 << 32 evaluate to 1 in Java?

Practice

Print the number of 1-bits in 255, in 256 and in -1, using Integer.bitCount.

Store four on/off settings (bold, italic, underline, strike) in one int, turn on bold and underline, then print which are on.

Without using % or /, print whether 37 and 48 are even, and print 48 divided by 8 using a shift.

Trade-offs

↔
Packing flags into an int is compact and fast to copy and compare, but it's cryptic; EnumSet gives the same performance with names and type safety.
↔
Bit tricks shrink code and avoid branches, but they're easy to get subtly wrong (signs, precedence, shift widths) and hard to review; use them where they express the idea, with a comment.

Done when you can

I can compute &, |, ^ and ~ by hand on small numbers.
I know the difference between <<, >> and >>>, including for negative numbers.
I know shift distances are masked and use 1L << for shifts past 31.
I can set, clear, toggle and test flag bits, with correct brackets.
I can use b & 0xFF to read a byte as unsigned and know the power-of-two test.

Command Palette

Words you'll meet

Step by step

01AND, OR, XOR column by column

02NOT and the -x - 1 rule

03Left shift multiplies by powers of two

04Two right shifts: >> and >>>

05Shift distances wrap around

06Flags in a single int

07Bit tricks you'll meet in interviews and the JDK

Try it yourself

Predict before you print

Add a permission

Find the unpaired number

Code & diagrams

Break it on purpose

Shift an int by 40

Forget brackets around a mask test

Put 0xFF into a byte

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can