Bit Manipulation

DSA · Algorithm Techniques

Theory

Bit manipulation works directly on the binary representation of integers using AND (&), OR (|), XOR (^), NOT (~) and shifts (<< and >>). Useful facts: x & 1 tells whether x is odd, x & (x-1) clears the lowest set bit, a ^ a = 0 and a ^ 0 = a. A bitmask can represent a set of up to 64 items in one integer.

Why we use it

Bit tricks are extremely fast, use little memory and solve some problems elegantly.

When to use it

Use them for flags and permissions, finding the single unique number, counting set bits, subsets via bitmasks, and checking powers of two.

How it works

  1. Number in binary
  2. Check bit i? Yes: (x >> i) & 1. No: Set: x | (1 << i); clear: x & ~(1 << i).
  3. x & (x - 1) clears the lowest set bit
  4. Operations run in O(1)

Syntax

x & 1            odd check
x & (x - 1)      clear lowest set bit
x & (x - 1) == 0 power of two (x > 0)
1 << k           k-th bit mask
a ^ b ^ a = b    XOR cancels pairs

Example

def count_bits(x):
    c = 0
    while x:
        x &= x - 1
        c += 1
    return c

def single_number(nums):
    r = 0
    for n in nums:
        r ^= n
    return r

READ, WRITE, ADMIN = 1, 2, 4
user = READ | WRITE
print("13 in binary:", bin(13), "| set bits:", count_bits(13))
print("Is 64 a power of two:", 64 & 63 == 0)
print("Single number in [4,1,2,1,2]:", single_number([4, 1, 2, 1, 2]))
print("User can write:", bool(user & WRITE), "| admin:", bool(user & ADMIN))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic