Interview Cake A bit shift moves each digit in a number's binary representation left or right. Shifting left by k places multiplies a number by 2^k (as long as no 1 bits fall off the end), and shifting a non-negative number right by k places divides it by 2^k, rounding down.
There are three main types of shifts. Here's how they compare:
| Left shift | Logical right shift | Arithmetic right shift | |
|---|---|---|---|
| In Java | << | >>> | >> |
| Bit that falls off | The most significant (leftmost) bit | The least significant (rightmost) bit | The least significant (rightmost) bit |
| Bit added | A 0 on the right | A 0 on the left | A copy of the most significant bit (the sign bit) on the left |
| Shifting by 1 | Multiplies by 2 | Divides a non-negative number by 2, rounding down | Divides by 2, rounding down, and keeps the sign |
| Example (4 bits) | 0011 → 0110 | 1011 → 0101 | 1011 → 1101 |
On fixed-size integers, a shift is a single, super fast processor instruction—O(1) time. That's why compilers often turn multiplying by a power of 2 into a left shift behind the scenes.
Left Shifts
When shifting left, the most-significant bit is lost, and a 0 bit is inserted on the other end.
The left shift operator is usually written as "<<".
A single left shift multiplies a binary number by 2:
Logical Right Shifts
When shifting right with a logical right shift, the least-significant bit is lost and a 0 is inserted on the other end.
For positive numbers, a single logical right shift divides a number by 2, throwing out any remainders.
Arithmetic Right Shifts
When shifting right with an arithmetic right shift, the least-significant bit is lost and the most-significant bit is copied.
Languages handle arithmetic and logical right shifting in different ways. Java provides two right shift operators: >> does an arithmetic right shift and >>> does a logical right shift.
The first two numbers had a 1 as the most significant bit, so more 1's were inserted during the shift. The last two numbers had a 0 as the most significant bit, so the shift inserted more 0's.
If a number is encoded using two's complement, then an arithmetic right shift preserves the number's sign, while a logical right shift makes the number positive.
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
