Bitwise Operators - Learning Module

Loading content...

0/276

OR — At Least One Bit Must Be 1

The Inclusive Nature of OR

If AND is the strict gatekeeper that demands unanimous agreement, then OR is the welcoming host that opens the door when anyone knocks. The OR operator embodies inclusivity at its core—it outputs a 1 whenever at least one input is 1, regardless of what the other input might be.

This inclusive nature mirrors everyday language. The statement "I'll be happy if I get a raise OR a promotion" is true if either condition (or both) is met. Unlike the exclusive "or" we sometimes use colloquially ("Would you like coffee or tea?"), the bitwise OR is always inclusive—it includes the possibility of both.

What You Will Learn

By the end of this page, you will master the OR operator's behavior, understand its hardware realization, and know how to apply it for setting bits, combining flags, constructing values from parts, and implementing efficient algorithms. You'll see how OR complements AND to provide a complete toolkit for bit manipulation.

The OR Operator Defined

The bitwise OR operator, typically represented by the | symbol (pipe character), performs a logical disjunction on each pair of corresponding bits from two operands. The result bit is 1 if at least one of the input bits is 1; the result is 0 only when both inputs are 0.

This behavior is the dual (or complement) of AND. Where AND demands both bits be 1, OR requires only one.

The Core Principle

Think of OR as an inclusive collector. It gathers all the 1s from both operands. A 1 in either input (or both) results in a 1 in the output. Only complete absence of 1s (both inputs 0) yields a 0. This makes OR perfect for combining, merging, and setting bits.

Formal Definition:

Given two binary values A and B, the OR operation is defined as:

A OR B = 1 if A = 1 OR B = 1 (or both)
A OR B = 0 if A = 0 AND B = 0

In mathematical notation, this can be expressed as:

A ∨ B = max(A, B) (where A, B ∈ {0, 1})

Or using the complementary relationship with AND:

A OR B = NOT(NOT A AND NOT B)  (De Morgan's Law)

This means OR can be thought of as: "NOT(both are 0)".

OR Truth Table
Bit A	Bit B	A OR B	Explanation
0	0	0	Neither bit is set → result is 0
0	1	1	Second bit is set → result is 1
1	0	1	First bit is set → result is 1
1	1	1	Both bits set → result is 1

Key Insight from the Truth Table:

Notice that three out of four possible input combinations result in 1. This is the exact inverse of AND's distribution. This asymmetry makes OR ideal for accumulation and union operations—it's an inclusive operator that combines the "on" bits from both inputs.

Hardware Origins — The OR Gate

Just as the AND gate has a physical realization, the OR gate is a fundamental component of digital circuits. Understanding its implementation illuminates why OR behaves as it does.

Transistor-Level Implementation:

An OR gate can be constructed using two transistors connected in parallel. Current can flow through the circuit if either transistor is on. Only when both transistors are off is the circuit fully open (no current flows).

This is the physical opposite of AND's series configuration. Parallel paths provide alternative routes for current, embodying the "at least one" logic of OR.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
      Voltage Source (+V)
             │
      ┌──────┴──────┐
      │             │
 ┌────┴────┐   ┌────┴────┐
 │   A     │   │   B     │   ← Parallel switches (transistors)
 │  (SW)   │   │  (SW)   │
 └────┬────┘   └────┬────┘
      │             │
      └──────┬──────┘
             │
             ▼
          OUTPUT
             │
             ▼
          Ground
 
If A = 1 OR B = 1 → At least one switch closed → Current flows → Output = 1
If A = 0 AND B = 0 → Both switches open → No current → Output = 0

Boolean Algebra Properties:

The OR operation follows these fundamental laws:

Identity Law: A OR 0 = A (ORing with 0 preserves the original value)
Domination Law: A OR 1 = 1 (ORing with 1 always yields 1)
Idempotent Law: A OR A = A (ORing a value with itself yields that value)
Commutative Law: A OR B = B OR A (order doesn't matter)
Associative Law: (A OR B) OR C = A OR (B OR C) (grouping doesn't matter)
Absorption Law: A OR (A AND B) = A
De Morgan's Law: NOT(A OR B) = (NOT A) AND (NOT B)

These laws are essential for simplifying complex Boolean expressions and optimizing bit manipulation code.

The Duality of AND and OR

AND and OR are duals in Boolean algebra. Every theorem involving AND has a corresponding theorem for OR obtained by swapping AND with OR and swapping 0 with 1. This principle of duality is powerful for deriving new identities and understanding the symmetry of Boolean logic.

Multi-Bit OR Operations

Like AND, the bitwise OR operator applies its single-bit logic independently to each corresponding bit position. When you OR two 32-bit integers, you're performing 32 parallel, independent OR operations—one for each bit position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   Operand A:    1 0 1 1 0 1 1 0  (decimal: 182)
   Operand B:    0 1 0 1 1 0 1 0  (decimal: 90)
                 ─────────────────
   A OR B:       1 1 1 1 1 1 1 0  (decimal: 254)
 
Position-by-position breakdown:
  Position 7: 1 OR 0 = 1
  Position 6: 0 OR 1 = 1
  Position 5: 1 OR 0 = 1
  Position 4: 1 OR 1 = 1
  Position 3: 0 OR 1 = 1
  Position 2: 1 OR 0 = 1
  Position 1: 1 OR 1 = 1
  Position 0: 0 OR 0 = 0
 
Notice: The result contains all the 1s from both inputs — it's a "union" of set bits.

The Union Interpretation:

If you think of each bit position as representing membership in a set (1 = member, 0 = not member), then OR performs a set union. The result contains every element that appears in either set (or both). This interpretation is fundamental to understanding bitmasks as sets.

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
// 8-bit integer OR operation
const a = 0b10110110; // 182 in decimal
const b = 0b01011010; // 90 in decimal
const result = a | b; // 0b11111110 = 254
 
console.log(result.toString(2).padStart(8, '0')); 
// Output: "11111110"
 
// Practical: Combining two 4-bit nibbles into one byte
const highNibble = 0b1010 << 4;  // 0b10100000
const lowNibble  = 0b0011;       // 0b00000011
const combined   = highNibble | lowNibble; // 0b10100011 = 163
 
console.log(combined.toString(2).padStart(8, '0'));
// Output: "10100011"
 
// Building a 32-bit value from four bytes
const byte3 = 0xAB;  // Most significant byte
const byte2 = 0xCD;
const byte1 = 0xEF;
const byte0 = 0x12;  // Least significant byte
 
const value = (byte3 << 24) | (byte2 << 16) | (byte1 << 8) | byte0;
console.log(value.toString(16).toUpperCase()); 
// Output: "ABCDEF12"

OR Never Reduces Bits

An important property: A | B >= max(A, B) for non-negative integers. OR never clears bits—it can only keep them or set them. The result always has at least as many 1-bits as either operand alone. This is crucial when combining flags or building values.

Setting Bits — The Primary Use Case

The most important application of OR is setting specific bits to 1 without affecting other bits. This is the conceptual opposite of AND's bit-clearing capability.

The Setting Principle:

Recall the Boolean laws:

A OR 0 = A (0 preserves the original bit)
A OR 1 = 1 (1 forces the bit to 1)

By creating a mask with 1s in positions we want to set and 0s in positions we want to leave unchanged, we can turn on arbitrary bits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Goal: Set bits 2 and 5 to 1, leave all other bits unchanged
 
Original Value:  1 0 0 1 0 0 0 1  (decimal: 145)
                 7 6 5 4 3 2 1 0  ← bit positions
 
Mask:            0 0 1 0 0 1 0 0  (0b00100100 = 36)
                 ─────────────────
                 Zeros: unchanged   Ones: will be set
 
Result:          1 0 1 1 0 1 0 1  (decimal: 181)
                     ↑     ↑
                 Bits 5 and 2 are now set!
 
Other bits remain exactly as they were.

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
// Set bit at position n
function setBit(value: number, n: number): number {
    const mask = 1 << n;  // Create mask with only bit n set
    return value | mask;
}
 
// Visual example:
// value:   10010001 (decimal 145)
// 1 << 5:  00100000 (bit 5 set)
// OR:      10110001 (decimal 177) — bit 5 now set!
 
const original = 0b10010001; // 145
const withBit5 = setBit(original, 5);
console.log(withBit5.toString(2).padStart(8, '0'));
// Output: "10110001" (177)
 
// Set multiple bits at once
function setBits(value: number, mask: number): number {
    return value | mask;
}
 
// Set bits 1, 3, and 6
const multiMask = 0b01001010; // Bits to set
const result = setBits(0b00000000, multiMask);
console.log(result.toString(2).padStart(8, '0'));
// Output: "01001010" — bits 1, 3, 6 are now 1

Idempotency: Setting Already-Set Bits

An important property of OR is idempotency with respect to 1s. ORing a bit that's already 1 with another 1 still yields 1. This means setting a bit that's already set has no effect—there's no "double setting" or overflow:

1 | 1 = 1  (not 10, not 2, just 1)

This is crucial for safe repeated flag operations. You can confidently add a flag without checking if it's already present.

The AND-OR Duality

AND with mask clears bits where mask has 0s, preserves where mask has 1s. OR with mask sets bits where mask has 1s, preserves where mask has 0s. They're complementary operations that together give complete control over individual bits.

Combining Flags and Options

One of the most widespread uses of OR is combining multiple flags into a single value. This pattern appears throughout systems programming, from file permissions to window styles to compilation options.

Why Flags Use OR:

When each flag occupies a unique bit position (typically each flag is a power of 2), ORing them together creates a composite value with multiple flags set. Because no two flags share bit positions, they don't interfere with each other.

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
32
// Define flags as individual bits (powers of 2)
const FileFlags = {
    READ:       0b00000001,  // 1
    WRITE:      0b00000010,  // 2
    EXECUTE:    0b00000100,  // 4
    HIDDEN:     0b00001000,  // 8
    SYSTEM:     0b00010000,  // 16
    ARCHIVE:    0b00100000,  // 32
    READONLY:   0b01000000,  // 64
    TEMPORARY:  0b10000000,  // 128
} as const;
 
// Combine flags using OR
const normalFile = FileFlags.READ | FileFlags.WRITE;
console.log(normalFile.toString(2).padStart(8, '0'));
// Output: "00000011" — READ and WRITE
 
const executable = FileFlags.READ | FileFlags.EXECUTE;
console.log(executable.toString(2).padStart(8, '0'));
// Output: "00000101" — READ and EXECUTE
 
const hiddenSystemFile = 
    FileFlags.READ | FileFlags.HIDDEN | FileFlags.SYSTEM;
console.log(hiddenSystemFile.toString(2).padStart(8, '0'));
// Output: "00011001" — READ, HIDDEN, and SYSTEM
 
// Add a flag to existing flags
let permissions = FileFlags.READ;
permissions = permissions | FileFlags.WRITE;  // Add WRITE
permissions |= FileFlags.EXECUTE;             // Shorthand: Add EXECUTE
console.log(permissions.toString(2).padStart(8, '0'));
// Output: "00000111" — READ, WRITE, and EXECUTE

Real-World Examples:

This pattern is ubiquitous in programming APIs:

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
32
33
34
35
36
// Pattern: Unix-style file open flags (conceptual)
const O_RDONLY   = 0x0000;  // Read-only
const O_WRONLY   = 0x0001;  // Write-only
const O_RDWR     = 0x0002;  // Read-write
const O_CREAT    = 0x0040;  // Create if doesn't exist
const O_EXCL     = 0x0080;  // Fail if exists (with O_CREAT)
const O_TRUNC    = 0x0200;  // Truncate to zero length
const O_APPEND   = 0x0400;  // Append mode
 
// Open file for writing, create if needed, truncate if exists
const flags = O_WRONLY | O_CREAT | O_TRUNC;
 
// Pattern: CSS-like text decorations as flags
const TextDecoration = {
    NONE:         0,
    UNDERLINE:    1 << 0,
    OVERLINE:     1 << 1,
    LINE_THROUGH: 1 << 2,
    BLINK:        1 << 3,
} as const;
 
const decoration = 
    TextDecoration.UNDERLINE | TextDecoration.LINE_THROUGH;
// Creates "strikethrough with underline" effect
 
// Pattern: Keyboard modifier keys
const Modifiers = {
    NONE:  0,
    SHIFT: 1 << 0,
    CTRL:  1 << 1,
    ALT:   1 << 2,
    META:  1 << 3,  // Cmd on Mac, Win key on Windows
} as const;
 
// User pressed Ctrl+Shift+S
const mods = Modifiers.CTRL | Modifiers.SHIFT;

Flag Design Best Practice

Always define flags as powers of 2 (1 << n) to ensure each occupies a unique bit position. Using 1 << n syntax is clearer than literal powers of 2 and reduces the chance of accidentally reusing a bit position.

Building Values from Parts

Beyond flags, OR is essential for assembling multi-part values where different bit ranges represent different components. This is fundamental in:

Color encoding (RGB, RGBA, HSL)
Network protocols (assembling headers)
Data serialization (packing structures)
Hardware interfacing (building register values)
Compression formats (constructing encoded data)

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
// RGB color: 8 bits each for Red, Green, Blue
// Format: 0xRRGGBB (24-bit color)
 
function makeRGB(r: number, g: number, b: number): number {
    // Ensure each component is 8 bits (0-255)
    r = r & 0xFF;
    g = g & 0xFF;
    b = b & 0xFF;
    
    // Shift each to its position and combine with OR
    return (r << 16) | (g << 8) | b;
}
 
const orange = makeRGB(255, 165, 0);
console.log(orange.toString(16).toUpperCase()); 
// Output: "FFA500"
 
// RGBA color: includes 8-bit alpha channel
// Format: 0xAARRGGBB or 0xRRGGBBAA depending on convention
 
function makeRGBA(r: number, g: number, b: number, a: number): number {
    return ((a & 0xFF) << 24) | ((r & 0xFF) << 16) | 
           ((g & 0xFF) << 8) | (b & 0xFF);
}
 
const semiTransparentRed = makeRGBA(255, 0, 0, 128);
console.log(semiTransparentRed.toString(16).toUpperCase());
// Output: "80FF0000" (128 alpha, 255 red, 0 green, 0 blue)

Assembling Network Packets:

Network protocols often pack multiple fields into headers. Here's how you might construct a simplified packet header:

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
// Simplified packet header (16 bits):
// Bits 14-15: Version (2 bits, 0-3)
// Bits 10-13: Type (4 bits, 0-15)
// Bits 0-9:   Length (10 bits, 0-1023)
 
function buildPacketHeader(
    version: number,  // 0-3
    type: number,     // 0-15
    length: number    // 0-1023
): number {
    // Mask each field to its allowed range, then shift and combine
    const versionBits = (version & 0b11) << 14;      // Bits 14-15
    const typeBits    = (type & 0b1111) << 10;        // Bits 10-13
    const lengthBits  = length & 0b1111111111;        // Bits 0-9
    
    return versionBits | typeBits | lengthBits;
}
 
const header = buildPacketHeader(2, 5, 512);
console.log(header.toString(2).padStart(16, '0'));
// Output: "1001010000000000"
//         ^^----version=2
//           ^^^^----type=5
//               ^^^^^^^^^^----length=512
 
// Decode for verification
const extractedVersion = (header >> 14) & 0b11;
const extractedType    = (header >> 10) & 0b1111;
const extractedLength  = header & 0b1111111111;
console.log({ extractedVersion, extractedType, extractedLength });
// Output: { extractedVersion: 2, extractedType: 5, extractedLength: 512 }

Prevent Field Overlap

When building multi-field values, always mask each component to its allowed bit width BEFORE shifting. If a component exceeds its range, the overflow bits will corrupt adjacent fields. The pattern (value & mask) << shift prevents this.

OR for Presence and Union Operations

When bits represent set membership, OR performs a set union. This interpretation is powerful for algorithms that track presence, combine results, or merge state.

Applications:

Visited tracking in graph algorithms
Capability merging in permission systems
Feature aggregation across configuration sources
Bloom filter operations
Bitmap indices in databases

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
// Represent sets as bitmasks
// Bit n is 1 if element n is in the set
 
const setA = 0b10110011;  // Elements: {0, 1, 4, 5, 7}
const setB = 0b01011100;  // Elements: {2, 3, 4, 6}
 
// Union: elements in A OR B
const union = setA | setB;
console.log(union.toString(2).padStart(8, '0'));
// Output: "11111111" — Elements: {0, 1, 2, 3, 4, 5, 6, 7}
 
// Helper to list elements in a bitmask set
function listElements(set: number): number[] {
    const elements: number[] = [];
    for (let i = 0; i < 32; i++) {
        if ((set & (1 << i)) !== 0) {
            elements.push(i);
        }
    }
    return elements;
}
 
console.log("Set A:", listElements(setA));  // [0, 1, 4, 5, 7]
console.log("Set B:", listElements(setB));  // [2, 3, 4, 6]
console.log("Union:", listElements(union)); // [0, 1, 2, 3, 4, 5, 6, 7]

Merging Configuration Options:

OR is useful when combining options from multiple sources with a "most permissive" policy—if any source enables an option, it's enabled in the result.

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
// Feature flags from different config sources
const Features = {
    DARK_MODE:    1 << 0,
    BETA_TESTING: 1 << 1,
    ANALYTICS:    1 << 2,
    PREMIUM:      1 << 3,
    OFFLINE:      1 << 4,
} as const;
 
// Config from different sources
const defaultConfig  = Features.ANALYTICS;  // Default: just analytics
const userPrefs      = Features.DARK_MODE | Features.OFFLINE;
const adminOverrides = Features.BETA_TESTING | Features.PREMIUM;
 
// Merge: enable feature if ANY source enables it
const finalConfig = defaultConfig | userPrefs | adminOverrides;
 
console.log("Final config:", finalConfig.toString(2).padStart(8, '0'));
// Output: "00011111" — All features enabled
 
// Check which features are enabled
const hasFeature = (config: number, feature: number) => 
    (config & feature) !== 0;
 
console.log("Has dark mode?", hasFeature(finalConfig, Features.DARK_MODE));   // true
console.log("Has premium?", hasFeature(finalConfig, Features.PREMIUM));       // true

OR is Additive, Never Subtractive

Remember that OR can only add 1s, never remove them. For merging with "any source can disable" semantics, you'd use AND instead. Choose OR for "any source can enable" (union) and AND for "all sources must enable" (intersection).

OR in Optimization Patterns

Beyond its direct uses, OR appears in several clever optimization patterns that exploit its properties.

Pattern 1: Convert to Boolean Without Branching

OR with zero is identity, but OR can help normalize non-zero values to 1 in certain contexts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Check if a number is non-zero (any bit set)
// Traditional: value !== 0
// Bitwise context: we want 0 or 1
 
function hasAnyBitSet(value: number): number {
    // Collapse all bits to position 0 using OR reductions
    // For a 32-bit value:
    let v = value;
    v = v | (v >> 16);  // Combine upper and lower 16 bits
    v = v | (v >> 8);   // Combine into lower 8 bits
    v = v | (v >> 4);   // Combine into lower 4 bits
    v = v | (v >> 2);   // Combine into lower 2 bits
    v = v | (v >> 1);   // Combine into bit 0
    return v & 1;       // Mask to get 0 or 1
}
 
console.log(hasAnyBitSet(0));         // 0
console.log(hasAnyBitSet(1));         // 1
console.log(hasAnyBitSet(0x80000000)); // 1 (only high bit set)
console.log(hasAnyBitSet(12345678));  // 1

Pattern 2: Branchless Maximum

OR can help compute maximum without conditional branches, which is useful in SIMD-style programming.

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
32
// Round up to the next power of 2
// Uses OR to propagate the highest set bit down
 
function nextPowerOf2(n: number): number {
    if (n <= 0) return 1;
    
    n--;  // Handle case where n is already a power of 2
    
    // Propagate the highest bit to all lower positions
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    
    return n + 1;
}
 
// How it works for n = 20:
// n = 19         = 0b00010011
// n |= n >> 1    = 0b00011011
// n |= n >> 2    = 0b00011111
// n |= n >> 4    = 0b00011111
// n |= n >> 8    = 0b00011111
// n |= n >> 16   = 0b00011111
// n + 1          = 0b00100000 = 32
 
console.log(nextPowerOf2(1));   // 1
console.log(nextPowerOf2(5));   // 8
console.log(nextPowerOf2(16));  // 16 (already power of 2)
console.log(nextPowerOf2(17));  // 32
console.log(nextPowerOf2(100)); // 128

The OR Propagation Pattern

The pattern of n |= n >> k for doubling k values (1, 2, 4, 8, 16) is a powerful technique for "smearing" the highest set bit to fill all lower positions. This creates a mask of 1s from the highest bit down, useful for power-of-2 operations and bit counting optimizations.

Summary: OR Operator Mastery

The OR operator is the natural complement to AND, providing the inclusive counterpart to AND's exclusive filtering. Let's consolidate what we've learned:

Key Takeaways

•Core Behavior: OR returns 1 when at least one input bit is 1. Only (0,0) yields 0.
•Truth Table Memory Aid: OR outputs 0 only when BOTH inputs are 0—it's the "unless both are off" operator.
•Hardware Foundation: OR gates use parallel transistor paths; either path conducting yields output.
•Setting Bits: Use OR with a mask to set specific bits. 1s in the mask set those bits; 0s preserve originals.
•Combining Flags: OR multiple power-of-2 flags to create composite values representing multiple options.
•Building Values: Use shift-then-OR to assemble multi-field values like colors or packet headers.
•Set Union: When bits represent set membership, OR computes the union.
•Idempotency: ORing a set bit with 1 still yields 1—safe for repeated flag additions.

OR Operator Quick Reference
Operation	Expression	Notes
Set bit n	`value \| (1 << n)`	Set bit to 1
Set multiple bits	`value \| mask`	Mask has 1s where to set
Combine flags	`flag1 \| flag2 \| flag3`	Each flag is power of 2
Build from parts	`(a << n) \| b`	Shift then combine
Set union	`setA \| setB`	Elements in either set
Propagate bits down	`n \|= n >> k`	Smear highest bit
Ensure minimum 1	`n \| 1`	Lowest bit always set

AND Summary

•Extracts bits (mask with 1s)
•Clears bits (mask with 0s)
•Set intersection
•Can only remove/preserve 1s

OR Summary

•Sets bits (mask with 1s)
•Preserves bits (mask with 0s)
•Set union
•Can only add/preserve 1s

What's Next:

With AND and OR understood, we'll explore XOR—the exclusive or operator that outputs 1 when inputs differ. XOR has unique properties that make it invaluable for toggling, swapping, encryption, and error detection.

Page Complete

You now have deep understanding of the OR bitwise operator—from its Boolean algebra roots to practical applications in setting bits, combining flags, building composite values, and computing set unions. Combined with AND, you have powerful tools for selective bit manipulation.