Bitwise Operators - Learning Module

Loading content...

0/276

NOT — Flip All Bits

The Universal Inverter

While AND, OR, and XOR are binary operators that combine two operands, NOT stands alone as a unary operator that transforms a single value. Its operation is conceptually the simplest: flip every bit. Every 0 becomes 1, every 1 becomes 0. No exceptions, no conditions.

Despite this apparent simplicity, NOT harbors subtle complexities—particularly when interacting with signed integers and two's complement representation. Understanding NOT fully requires grasping how computers represent negative numbers, why ~5 doesn't equal what you might initially expect, and how to wield NOT effectively for mask creation and bit manipulation.

What You Will Learn

By the end of this page, you will understand NOT's bit-flipping behavior, its relationship with two's complement arithmetic, the surprising results of applying NOT to signed integers, and practical techniques for using NOT to create inverted masks and perform bit-clearing operations. You'll also learn to avoid common pitfalls that trip up even experienced programmers.

The NOT Operator Defined

The bitwise NOT operator, typically represented by the ~ symbol (tilde), performs a logical negation on each bit of its single operand. Every bit is inverted: 0 becomes 1, and 1 becomes 0. This operation is also called the one's complement of the value.

Unlike the binary operators we've discussed, NOT takes only one operand.

The Core Principle

Think of NOT as a universal bit flipper or total inverter. It creates the bitwise mirror image of the input—where there was presence (1), there's now absence (0), and vice versa. This total inversion is what makes NOT powerful for creating complementary masks.

Formal Definition:

Given a binary value A, the NOT operation is defined as:

NOT 0 = 1
NOT 1 = 0

Or equivalently:

NOT A = 1 - A (where A ∈ {0, 1})

For an n-bit value, NOT inverts all n bits independently.

NOT Truth Table
Input A	NOT A	Explanation
0	1	Absence becomes presence
1	0	Presence becomes absence

The Simplest Truth Table:

NOT has the simplest possible truth table—just two rows. Yet its effects, especially when combined with other operators and signed integer representation, can be profoundly tricky. The simplicity is deceptive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
   Original:  1 0 1 1 0 1 1 0  (decimal: 182)
               ─────────────────
   NOT:        0 1 0 0 1 0 0 1  (decimal: 73, but see below...)
 
Position-by-position:
  Position 7: NOT 1 = 0
  Position 6: NOT 0 = 1
  Position 5: NOT 1 = 0
  Position 4: NOT 1 = 0
  Position 3: NOT 0 = 1
  Position 2: NOT 1 = 0
  Position 1: NOT 1 = 0
  Position 0: NOT 0 = 1
 
Every single bit is inverted — complete mirror image!

NOT and Two's Complement

Here's where NOT becomes interesting—and potentially confusing. Most computers use two's complement representation for signed integers. In this system, the NOT operation has a surprising mathematical property:

~n = -(n + 1)

This means:

~0 = -1
~1 = -2
~5 = -6
~(-1) = 0

Wait, what? Let's understand why.

Two's Complement Refresher:

In two's complement (for n-bit integers):

Positive numbers are represented normally (0 to 2^(n-1) - 1)
Negative numbers are represented as 2^n - |value| (or equivalently, invert all bits and add 1)
The most significant bit (MSB) indicates sign: 0 = positive, 1 = negative

For 8-bit signed integers:

0 = 00000000
1 = 00000001
127 = 01111111 (maximum positive)
-1 = 11111111 (all 1s!)
-2 = 11111110
-128 = 10000000 (minimum negative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// In two's complement: ~n = -(n+1)
 
// Let's verify with 8-bit signed interpretation:
// 5 = 0b00000101
// ~5 = 0b11111010
 
// In two's complement, 0b11111010 represents:
// It's negative (MSB = 1)
// To find magnitude: invert bits → 0b00000101 = 5, add 1 → 6
// So it represents -6
 
console.log(~5);   // -6
console.log(~0);   // -1
console.log(~1);   // -2
console.log(~(-1)); // 0
console.log(~(-5)); // 4
 
// The relationship: ~n + n = -1 (all 1s in binary)
// Therefore: ~n = -1 - n = -(n + 1)
 
// Proof:
// n + ~n gives us all 1s (each bit position is 0+1 or 1+0)
// All 1s in two's complement is -1
// So: n + ~n = -1
// Therefore: ~n = -1 - n = -(n+1)
 
for (let n = -10; n <= 10; n++) {
    console.log(`~${n} = ${~n}, expected: ${-(n + 1)}, match: ${~n === -(n + 1)}`);
}

The Identity ~n = -(n+1)

This identity is crucial. When you see ~ applied to a number, mentally translate it to -(n+1). This explains why ~0 = -1 (not some large positive number), why ~(-1) = 0, and why ~n is never positive for non-negative n (in signed interpretation).

Hardware Implementation

The NOT gate is the simplest of all logic gates, requiring only a single transistor pair. It's also known as an inverter in digital electronics.

Transistor Implementation:

In CMOS technology, an inverter uses one NMOS and one PMOS transistor in a complementary configuration. When the input is high (1), the NMOS conducts and pulls the output low (0). When the input is low (0), the PMOS conducts and pulls the output high (1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
                VDD (+V)
                  │
             ┌────┴────┐
             │  PMOS   │ ← P-type transistor
      INPUT ─┼─────────┤
             │  NMOS   │ ← N-type transistor
             └────┬────┘
                  │
                 GND
 
Operation:
- When INPUT = 0: PMOS ON, NMOS OFF → OUTPUT pulled to VDD → OUTPUT = 1
- When INPUT = 1: PMOS OFF, NMOS ON → OUTPUT pulled to GND → OUTPUT = 0
 
The inverter is the fundamental building block of digital logic.
All other gates can be constructed using combinations of inverters and transistors.

Performance Characteristics:

NOT is typically the fastest gate operation (single stage of transistors)
Propagation delay: ~1 gate delay
Power consumption: minimal static, some dynamic during switching

In a CPU's ALU, NOT is typically implemented in parallel across all bits, completing in a single cycle just like AND, OR, and XOR.

De Morgan's Laws:

NOT interacts with AND and OR through De Morgan's laws, enabling powerful gate transformations:

NOT(A AND B) = (NOT A) OR (NOT B)
NOT(A OR B) = (NOT A) AND (NOT B)

These laws are fundamental to digital circuit design and Boolean expression simplification.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// De Morgan's Laws in code
function verifyDeMorgan(a: number, b: number): void {
    // Law 1: ~(a & b) = (~a) | (~b)
    const law1Left = ~(a & b);
    const law1Right = (~a) | (~b);
    console.log(`~(a & b) = ${law1Left}, (~a) | (~b) = ${law1Right}, equal: ${law1Left === law1Right}`);
    
    // Law 2: ~(a | b) = (~a) & (~b)
    const law2Left = ~(a | b);
    const law2Right = (~a) & (~b);
    console.log(`~(a | b) = ${law2Left}, (~a) & (~b) = ${law2Right}, equal: ${law2Left === law2Right}`);
}
 
verifyDeMorgan(0b10101010, 0b11001100);
// Both laws hold for all values!
 
// Practical use: Simplifying expressions
// If you need "not both set", you could use:
// ~(flags & BOTH_FLAGS) — but this inverts ALL bits
// Better: Check if either is missing
// (~flags) & BOTH_FLAGS will tell you which are missing

NAND and NOR

The NAND gate (NOT-AND) and NOR gate (NOT-OR) are universal gates—any Boolean function can be built using only NAND gates (or only NOR gates). This makes them crucial in chip manufacturing, where minimizing gate types reduces complexity. NAND = ~(A & B), NOR = ~(A | B).

Creating Inverted Masks

The most common practical use of NOT in bit manipulation is creating inverted masks. When you need a mask with 1s everywhere except certain positions, NOT provides an elegant solution.

The Pattern:

Create a mask with 1s in the positions you DON'T want
Apply NOT to invert it
Result: 1s everywhere except those positions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Goal: Clear bit at position n
// Need a mask with all 1s EXCEPT position n
 
function createClearMask(n: number): number {
    const bitToPreserve = 1 << n;  // Single 1 at position n
    return ~bitToPreserve;          // All 1s EXCEPT position n
}
 
// Example: Clear bit 4
const mask = createClearMask(4);
console.log((mask >>> 0).toString(2));  // "11111111111111111111111111101111"
//                                                                   ^ bit 4 is 0
 
// Apply to clear bit 4 from a value
const value = 0b11111111;
const cleared = value & mask;
console.log(cleared.toString(2)); // "11101111" (bit 4 cleared)
 
// Goal: Create mask for lower n bits, then invert for upper bits
function upperBitsMask(n: number): number {
    const lowerMask = (1 << n) - 1;  // n lower 1s
    return ~lowerMask;               // All upper bits
}
 
// Get upper 28 bits of a 32-bit value
const upper28Mask = upperBitsMask(4);
console.log((upper28Mask >>> 0).toString(16)); // "fffffff0"

Clearing Bits Pattern (Revisited with NOT):

Recall from our AND discussion: to clear specific bits, use value & ~mask where mask has 1s in positions to clear. NOT transforms "bits to clear" into "bits to keep."

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Clear specific bits while preserving others
const Flags = {
    A: 1 << 0,  // bit 0
    B: 1 << 1,  // bit 1
    C: 1 << 2,  // bit 2
    D: 1 << 3,  // bit 3
} as const;
 
let state = 0b1111;  // All flags set
 
// Remove flags B and C
const toRemove = Flags.B | Flags.C;  // 0b0110
state = state & ~toRemove;           // 0b1111 & 0b1001 = 0b1001
 
console.log(state.toString(2)); // "1001" — B and C cleared, A and D remain
 
// This pattern is so common, many developers use the shorthand:
state = 0b1111;
state &= ~(Flags.B | Flags.C);  // Combined assignment
console.log(state.toString(2)); // "1001"

The Clear Pattern

The pattern value &= ~mask is your go-to for clearing bits. Read it as: "Keep all bits AND NOT the ones in mask." The NOT inverts your "bits to clear" into "bits to preserve," and AND does the filtering.

Finding Two's Complement Negation

NOT is closely related to negation in two's complement. To negate a number (compute -n), the formula is:

-n = ~n + 1

This is the definition of two's complement negation: invert all bits (one's complement), then add 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// The relationship: -n = ~n + 1
// Therefore: ~n = -n - 1 = -(n + 1) [as we saw earlier]
 
function negateViaBits(n: number): number {
    return ~n + 1;
}
 
// Test
console.log(negateViaBits(5));   // -5
console.log(negateViaBits(-5));  // 5
console.log(negateViaBits(0));   // 0
 
// Why this works:
// n in binary:           00000101 (5)
// ~n (one's complement): 11111010
// ~n + 1:               11111011 (which is -5 in two's complement)
 
// Visual verification for 8-bit:
// 5 = 00000101
// -5 should be 256 - 5 = 251 = 11111011
// ~5 = 11111010 = 250
// ~5 + 1 = 251 = 11111011 ✓
 
// Another way to think about it:
// n + ~n = all 1s = -1 (in two's complement)
// So: ~n = -1 - n
// And: ~n + 1 = -1 - n + 1 = -n

Practical Application: Absolute Value Without Branching

We can use NOT in a branchless absolute value computation. This is useful in performance-critical code where branch mispredictions are costly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Traditional absolute value
function absTraditional(n: number): number {
    return n < 0 ? -n : n;
}
 
// Branchless absolute value (for 32-bit integers)
function absBranchless(n: number): number {
    // Create mask: 0 if positive, -1 (all 1s) if negative
    const mask = n >> 31;  // Arithmetic shift: sign bit replicated
    
    // XOR with mask flips bits if negative, no-op if positive
    // Add mask (0 or -1) to complete the two's complement if needed
    return (n ^ mask) - mask;
}
 
// How it works for n = -5:
// n = -5 = 0xFFFFFFFB (in 32-bit signed)
// mask = n >> 31 = 0xFFFFFFFF (-1)
// n ^ mask = 0xFFFFFFFB ^ 0xFFFFFFFF = 0x00000004 (which is 4)
// (n ^ mask) - mask = 4 - (-1) = 5 ✓
 
// For n = 5:
// n = 5 = 0x00000005
// mask = n >> 31 = 0x00000000 (0)
// n ^ mask = 5 ^ 0 = 5
// (n ^ mask) - mask = 5 - 0 = 5 ✓
 
console.log(absBranchless(-5));  // 5
console.log(absBranchless(5));   // 5
console.log(absBranchless(-100)); // 100
console.log(absBranchless(0));   // 0

When to Use Branchless

Branchless techniques like this are micro-optimizations. Modern CPUs have excellent branch prediction, so the benefit is often minimal. Use branchless code when you've profiled and confirmed branch mispredictions are a bottleneck, or in SIMD contexts where branchless is required. Otherwise, prefer readable conditional code.

Common Pitfalls with NOT

NOT is deceptively simple, but several pitfalls trap even experienced programmers.

Pitfall 1: Unexpected Sign Changes

Because ~n = -(n+1), applying NOT to a non-negative number always produces a negative result (in signed interpretation).

1
2
3
4
5
6
7
8
9
10
11
12
13
// You might expect ~5 to give you something like "the other bits"
// But in a 32-bit signed context:
console.log(~5);  // -6, not some positive number!
 
// If you want only the lower 8 bits inverted:
const byte = 0b10110101;
const inverted8bit = (~byte) & 0xFF;  // Mask to 8 bits
console.log(inverted8bit.toString(2).padStart(8, '0')); // "01001010"
 
// Without masking:
console.log(~byte);  // -182 (because of sign extension)
 
// Rule: After NOT, mask to the bit width you care about!

Pitfall 2: Bit Width Assumptions

NOT operates on all bits of the operand type. If you're thinking in terms of 8 bits but operating on 32-bit integers, you'll get unexpected high bits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// You have an 8-bit value and want its complement
const original = 0x0F;  // 0b00001111 — lower nibble set
const complement = ~original;
 
// You might expect: 0xF0 (0b11110000)
// But you get: 0xFFFFFFF0 (sign-extended to 32 bits!)
 
console.log(complement);  // -16 (which is 0xFFFFFFF0)
console.log(complement.toString(16));  // "-10" (confusing!)
 
// Solution: Mask to your desired width
const complement8bit = (~original) & 0xFF;
console.log(complement8bit.toString(16));  // "f0" ✓
 
// Or use unsigned right shift to see all bits
console.log((complement >>> 0).toString(16));  // "fffffff0"

Pitfall 3: NOT vs Logical Negation

Don't confuse bitwise NOT (~) with logical NOT (!). They behave very differently!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Bitwise NOT (~): Flips every bit
console.log(~0);   // -1 (all bits flipped to 1)
console.log(~1);   // -2
console.log(~5);   // -6
 
// Logical NOT (!): Converts to boolean and inverts
console.log(!0);   // true (0 is falsy, inverted to true)
console.log(!1);   // false (1 is truthy, inverted to false)
console.log(!5);   // false (5 is truthy)
 
// Double logical NOT for boolean conversion
console.log(!!0);  // false
console.log(!!5);  // true
 
// Common mistake: Using ~ when you meant !
const flags = 0;
// Wrong: if (~flags) — this is truthy because ~0 = -1
// Right: if (!flags) — this checks if flags is falsy
 
// Another gotcha: ~(-1) = 0, which is falsy!
// So ~value is truthy for all values except -1

The ~(-1) = 0 Gotcha

Because ~(-1) = 0, some code uses ~arr.indexOf(x) as a truthy check: if indexOf returns -1 (not found), ~(-1) = 0 is falsy. This is clever but obscure. Prefer arr.includes(x) or explicit comparison for readability.

NOT in Bit Manipulation Idioms

NOT appears in many classic bit manipulation idioms. Let's explore the most important ones.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 1. Clear the rightmost set bit: n & (n - 1)
//    Works because n-1 flips the rightmost 1 and all bits below it
function clearRightmostSetBit(n: number): number {
    return n & (n - 1);
}
console.log(clearRightmostSetBit(0b1010).toString(2)); // "1000"
console.log(clearRightmostSetBit(0b1100).toString(2)); // "1000"
 
// 2. Isolate the rightmost set bit: n & (-n) or n & (~n + 1)
//    Uses two's complement property: -n = ~n + 1
function isolateRightmostSetBit(n: number): number {
    return n & (-n);
}
console.log(isolateRightmostSetBit(0b1010).toString(2)); // "10"
console.log(isolateRightmostSetBit(0b1100).toString(2)); // "100"
 
// 3. Propagate rightmost set bit to the right: n | (n - 1)
function propagateRightmost(n: number): number {
    return n | (n - 1);
}
console.log(propagateRightmost(0b1010).toString(2));  // "1011"
console.log(propagateRightmost(0b10100).toString(2)); // "10111"
 
// 4. Turn off rightmost 1-bits (until all turned off)
function turnOffRightmost1s(n: number): number {
    // Only works if there's a 0 to the right of 1s
    // Sets rightmost 0 that has 1s to its right
    return ((n | (n - 1)) + 1) & n;
}

Creating Bit Ranges:

NOT is useful for creating masks that cover bit ranges.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Create mask for bits from 'start' to 'end' (inclusive)
function bitRangeMask(start: number, end: number): number {
    // Create mask with bits 0 through 'end' set
    const upperMask = (1 << (end + 1)) - 1;  // e.g., end=4 → 0b11111
    
    // Create mask with bits 0 through 'start-1' set
    const lowerMask = (1 << start) - 1;       // e.g., start=2 → 0b11
    
    // XOR to get only bits from start to end
    return upperMask ^ lowerMask;             // 0b11111 ^ 0b11 = 0b11100
}
 
console.log(bitRangeMask(2, 4).toString(2)); // "11100" (bits 2,3,4)
console.log(bitRangeMask(0, 3).toString(2)); // "1111" (bits 0,1,2,3)
console.log(bitRangeMask(4, 7).toString(2)); // "11110000" (bits 4,5,6,7)
 
// Alternative using NOT:
function bitRangeMaskAlt(start: number, end: number): number {
    // ~0 is all 1s, shift left to clear lower bits, then NOT higher bits
    const allOnes = ~0 >>> 0;  // 0xFFFFFFFF
    const lowClear = allOnes << start;
    const highClear = allOnes >>> (31 - end);
    return lowClear & highClear;
}

~0 is All Ones

~0 (NOT zero) produces a value with all bits set to 1. In two's complement, this is -1. It's useful as a starting point for creating masks: you can shift ~0 left or right to create partial masks, then combine with other operations.

NOT with Unsigned Interpretation

In some contexts, you want to treat values as unsigned integers. JavaScript's >>> (unsigned right shift) operator can help view the bit pattern without signed interpretation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// By default, JS shows ~ results as signed
console.log(~0);           // -1 (signed interpretation)
console.log(~0xFF);        // -256 (signed)
 
// Use >>> 0 to convert to unsigned 32-bit interpretation
console.log((~0) >>> 0);           // 4294967295 (0xFFFFFFFF as unsigned)
console.log((~0xFF) >>> 0);        // 4294967040 (0xFFFFFF00 as unsigned)
console.log((~0xFFFFFFFF) >>> 0);  // 0
 
// This is useful for seeing the actual bit pattern
const value = 0b10101010;
const notted = ~value;
console.log(notted);                          // -171 (confusing!)
console.log((notted >>> 0).toString(2));       // "11111111111111111111111101010101"
console.log((notted >>> 0).toString(16));      // "ffffff55"
 
// For 8-bit work, mask after NOT:
console.log(((~value) & 0xFF).toString(2).padStart(8, '0')); // "01010101" ✓

BigInt for Larger Values:

For values larger than 32 bits, JavaScript's BigInt type supports bitwise operations including NOT.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// BigInt for 64-bit and beyond
const big = 0x123456789ABCDEFn;
const notBig = ~big;
 
console.log(notBig.toString(16)); // "-123456789abcdf0" (still signed!)
 
// To work with specific bit widths in BigInt:
function notBigUnsigned(value: bigint, bits: number): bigint {
    const mask = (1n << BigInt(bits)) - 1n;  // e.g., 64 bits
    return (~value) & mask;
}
 
const value64 = 0x0000000000000001n;
const notted64 = notBigUnsigned(value64, 64);
console.log(notted64.toString(16)); // "fffffffffffffffe"

Language Differences

Different languages handle NOT differently. In C/C++, NOT's result depends on the operand type (signed/unsigned). In Java, ~ always operates on signed types. In Python, integers have arbitrary precision, so ~n = -(n+1) always, with no overflow. Know your language's semantics!

Summary: NOT Operator Mastery

The NOT operator's simplicity—flip every bit—belies its nuanced behavior when combined with signed integer representation. Mastering NOT requires understanding both its pure bitwise effect and its arithmetic implications in two's complement systems.

Key Takeaways

•Core Behavior: NOT flips every bit. 0 becomes 1, 1 becomes 0. Total inversion.
•Two's Complement Relationship: ~n = -(n + 1). This is NOT the bitwise complement alone!
•Negation Formula: -n = ~n + 1. Invert bits and add 1 for two's complement negation.
•Creating Clear Masks: Use ~mask to create a mask that preserves all bits except those in mask.
•Bit Width Awareness: NOT operates on all bits of the operand type; mask to desired width afterward.
•~0 = -1 = All 1s: This is a useful constant for creating masks.
•NOT vs !: Bitwise NOT (~) is different from logical NOT (!). Don't confuse them.
•~(-1) = 0: The only value that NOTs to a falsy result. Be aware of this edge case.

NOT Operator Quick Reference
Operation	Expression	Notes
Invert all bits	`~value`	0↔1 for every bit
Clear bit n	`value & ~(1 << n)`	Inverted single-bit mask
Clear mask bits	`value & ~mask`	Keep all except mask
Negate (two's comp)	`~value + 1`	Same as `-value`
All 1s constant	`~0`	Equals -1 (signed)
8-bit complement	`(~value) & 0xFF`	Mask to desired width
Unsigned view	`(~value) >>> 0`	Interpret as unsigned 32-bit

What's Next:

With all four fundamental bitwise operators—AND, OR, XOR, and NOT—now mastered, you have the complete foundation for bit manipulation. The next page will consolidate everything with comprehensive truth tables, combined examples, and practical exercises that use all operators together.

Page Complete

You now have deep mastery of the NOT bitwise operator—from its simple bit-flipping definition through its nuanced relationship with two's complement arithmetic, to practical applications in mask creation and classic bit manipulation idioms. Combined with AND, OR, and XOR, you have a complete toolkit for low-level bit manipulation!