AlgoViz
HomeBit Manipulation

Introduction to Bits and Tricks

Easy

AND, OR, XOR and the shifts

Problem

Learn binary representation and the core bit operations: AND, OR, XOR, NOT, and left/right shifts.

In simple words

Numbers are rows of on/off switches; AND/OR/XOR combine them switch by switch.

The idea

Every integer is a row of bits, and the bitwise operators act on all of them at once. AND masks bits off, OR turns them on, XOR flips them and detects difference, and shifting left or right multiplies or divides by powers of two — which is why bit tricks are constant-time where loops would not be.

The trick

  • `x & 1` tests the lowest bit; `x >> i & 1` tests bit i.
  • x ^ x = 0 and x ^ 0 = x — the identities behind every 'find the odd one out' trick.
  • `x & (x-1)` clears the lowest set bit; `x & -x` isolates it.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

5
3
0
1

Step 1 of 2. Here's the example — 5 & 3 Values: 5, 3.

1/2
Optimal
timeO(1)spaceO(1)
1a & b   // both on2a | b   // either on3a ^ b   // exactly one on4a << k  // multiply by 2^k5a >> k  // divide by 2^k

Input

array
[5, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
5 & 3
Output:
1

Example 2

Input:
5 | 2
Output:
7

Finished the walkthrough? Add it to your streak.