Inside AND: Beyond Bit Manipulation
This article is part of my Bit Manipulation Series.
If you want more bit manipulation tips, tricks, and problem-solving patterns, explore the full series here: 🔗 Bit Manipulation Series.
In this article, we'll develop a clear intuition for AND through its core properties, mental models, and real-world examples, the kind that prove invaluable in interviews, competitive programming, and low-level systems programming.
Section-1: Foundations and Intuition of AND
1.1 AND as Logical Conjunction
In propositional logic, P ∧ Q is read as: "P and Q”.
The compound proposition is true only if both propositions are true simultaneously.
1.2. AND as Consensus and Simultaneous Truth
In Boolean algebra, AND operates on binary values.
Truth survives only under unanimous agreement.
AND computes the minimum truth value under the ordering 0 < 1
min(0,0) = 0
min(0,1) = 0
min(1,0) = 0
min(1,1) = 1
This gives AND a natural interpretation as the coexistence of requirements. Example:
Door opens if: Key inserted AND password correct
Access granted if: Authenticated AND authorized
Processor proceeds if: Data ready AND execution slot available
Each additional AND introduces another condition that must hold simultaneously.
1.3. AND as Commonality Extraction
When applied to bit representations, AND preserves only what is shared by all operands.
Suppose bits encode features.
Bit 0 → feature A
Bit 1 → feature B
Bit 2 → feature C
Bit 3 → feature D
Consider 2 objects:
1110 (Object1)
1011 (Object2)
----
1010 (Only shared features remain)
AND suppresses uniqueness and emphasizes agreement.
AND extracts the stable structural core.
- AND behaves like set intersection, but on bit positions.
Variable bits disappear. Stable bits survive.
Input = common structure + variability.
Output = common structure
AND never combines information. It only retains what already existed in all inputs simultaneously. This interpretation naturally extends to problems involving agreement.
Suppose bit positions represent permissions.
Bit 0 → Read
Bit 1 → Write
Bit 2 → Execute
Bit 3 → Admin
Users:
1110
1010
1011
-------
Cumulative AND:
1010
Interpretation of 1010:
Read → shared
Execute → shared
Write → not universal
Admin → not universal
Thus, AND identifies properties that hold universally across a collection.
1.4. Set Interpretation of Bits
A bitmask can be viewed as a set.
If bit i is set (1), interpret it as: element i belongs to the set.
13 = 1101₂ > Represents {0, 2, 3}
Because:
bit 0 = 1
bit 2 = 1
bit 3 = 1
11 = 1011₂ > Represents {0,1,3}
AND(13, 11):
1101
1011
----
1001 > Represents {0,3}
This matter because Many bitmask problems are secretly set problems.
Viewing bitmasks as sets often transforms seemingly difficult bitwise problems into familiar set operations. Example:
Common skills among candidates:
Java → bit 0
SQL → bit 1
Graphs → bit 2
DP → bit 3
Candidate A skills: 1110
Candidate B skills: 1011
Common skills: 1010
Section-2: Behavioral Rules of AND
2.1 AND Never Creates 1s
The most fundamental behavioral property of AND is: AND preserves existing 1-bits; it never creates new ones.
For any bit position:
1 AND 1 → 1
1 AND 0 → 0
0 AND 1 → 0
0 AND 0 → 0
AND only removes bits. It never introduces them.
This seemingly simple observation underlies many greedy algorithms and optimization techniques involving bitmasks.
2.2 Monotonicity of AND
Since AND cannot create new 1-bits, its value can only remain the same or decrease.
For any integers:
a & b <= a
a & b <= b
Thus, applying additional AND operations never increases the result.
AND is monotonic non-increasing.
Subarray AND Sequence is Monotonic
// Fix left endpoint.
A[l]
A[l] & A[l+1]
A[l] & A[l+1] & A[l+2]
...
// The sequence is monotonic non-increasing.
1111
1101
1001
1000
1000
Bits may disappear.
They never reappear.
For any operands:
popcount(A & B) ≤ popcount(A)
popcount(A & B) ≤ popcount(B)
Extending a subarray can only preserve or remove information.
2.3 AND as Constraint Accumulation
Monotonicity provides another interpretation of AND.
Each additional operand introduces another requirement that must be satisfied.
System state
↓
Apply condition 1
↓
Apply condition 2
↓
Apply condition 3
↓
Remaining valid states
AND progressively accumulates constraints.
AND Only Removes Information: Once a bit becomes 0: It cannot be recovered through further AND operations.
AND exhibits one-way information loss.
Many states
↓
Fewer states
↓
Even fewer states
2.4 Why the Number of Distinct AND Values ≤ 32?
A particularly important consequence of monotonicity is that the number of distinct AND values remains small.
Suppose array elements are 32-bit integers.
Consider repeatedly extending a subarray:
x
x & a
x & a & b
x & a & b & c
...
Every new AND value can only be formed by turning some 1-bits into 0.
To obtain a new distinct value:
At least one bit must flip from
1 → 0.
However:
Once a bit becomes
0, it can never become1again.
Since there are only 32 bit positions:
Each bit can disappear at most once.
Therefore, there can be at most 32 distinct AND values at any index.
Thus:
Maximum distinct AND values ≤ 32
2.5. Range AND
Range AND inherits all previously discussed properties.
Range AND Never Increases. Adding more numbers can only remove bits.
For any range:
a & b ≤ a
a & b ≤ b
Range AND Stabilizes Quickly: Distinct AND values generated while extending a subarray are at most: O(log V), where V = maximum value
Every new AND operation can only turn bits OFF.
Range AND = Common Binary Prefix
while (L < R)
R &= (R - 1);
L = 26 = 11010
R = 31 = 11111
// Common prefix: 11
26 & 31 = 11000
AND of Consecutive Numbers:
Large ranges rapidly become 0, because every bit eventually flips.
A bit survives final AND if: Every number contains that bit.
Section-3: The Information Theory of AND
The behavioral properties of AND discussed earlier have a deeper explanation:
AND is an information-reducing operation.
Unlike operations that accumulate information, bitwise AND progressively filters away distinctions until only universally supported facts remain.
3.1 AND as Information Filtering
Bitwise AND acts as an information filter.
Each bit position is tested independently:
If every operand contains the bit, it survives.
If even one operand lacks the bit, it disappears.
Thus, AND selectively preserves only the information that is universally supported.
Input information
↓
Remove unsupported bits
↓
Retain only guaranteed information
Unlike OR, which accumulates possibilities, AND extracts necessities.
A surviving bit represents a property that was true in every input.
A removed bit represents uncertainty:
At least one input failed to support that property.
Thus, AND transforms a collection of observations into their shared certainty.
3.2 Loss of Distinguishing Information
Because AND preserves only common information, it inevitably discards distinctions between inputs.
Different inputs can therefore produce exactly the same output.
1111 & 1100 = 1100
1100 & 1100 = 1100
1101 & 1110 = 1100
1110 & 1101 = 1100
The output tells us:
These bits survived universally.
However, it tells us nothing about:
Which bits disappeared first?
Which operand caused their removal?
What the original operands were?
Thus:
AND is a many-to-one mapping.
Many different input combinations collapse into the same result.
The operation preserves consensus while destroying individuality.
3.3 Non-invertibility of AND
Because information is discarded, AND cannot be inverted.
Given an output:
x & y = z
there is generally no unique way to recover x and y.
For example:
1111 & 1100 = 1100
1100 & 1100 = 1100
1101 & 1110 = 1100
all produce the same result:
1100
From the output alone, we cannot determine which input pair generated it.
Therefore:
AND is non-invertible.
The original information has been irreversibly compressed.
3.4 Why Prefix AND Cannot Be Inverted
This information-loss perspective has important algorithmic consequences.
Prefix sums work because addition preserves enough information to allow reversal.
sum(l,r) = prefix[r] − prefix[l−1]
prefix[i] = arr[0] + arr[1] + ... + arr[i]
prefixAND[i] = arr[0] & arr[1] & ... & arr[i]
AND(l,r) cannot be recovered from previous prefix values.
There exists no operation analogous to subtraction that can "undo" AND.
Once a bit disappears from a prefix AND, its origin is lost forever.
Thus:
Prefix AND is not decomposable in the same way as prefix sums.
This explains why many range-sum techniques fail for AND problems, forcing us to exploit monotonicity instead.
Section-4: The Mathematical Structure Behind AND
The previous sections described what AND means, how it behaves, and what information it preserves. In this section, we examine the mathematical structures that give rise to these behaviors.
4.1 Fundamental Algebraic Properties
Commutativity A ∧ B = B ∧ A
Order Does Not Matter
AND does not assign importance to operands.
Thus,
Authenticated ∧ Authorized === Authorized ∧ Authenticated
It only asks which conditions hold simultaneously?
Associativity(A ∧ B) ∧ C = A ∧ (B ∧ C)
Grouping Does Not Matter
Multiple constraints can be accumulated in any sequence. Thus requires no specific evaluation structure.
This allows cumulative AND computations to be decomposed into smaller pieces and combined later.
Associativity enables data structures such as segment trees to answer range AND queries efficiently.
Idempotence A ∧ A = A
Repetition Has No Effect
Applying the same constraint repeatedly provides no additional restriction.
For example: If "The user must be authenticated” is already enforced, then enforcing it again contributes nothing.
AND depends on which conditions exist, not how many times they appear.
Idempotence is one of the reasons sparse tables can answer static range AND queries efficiently.
Identity A ∧ 1 = A preserve all information.
Absorbing A ∧ 0 = 0 destroy all information.
4.2 Order-Theoretic Interpretation
All bitmasks of n bits form a structure called Boolean lattice.
111
/ | \
110 101 011
| \ | / |
100 010 001
\ | /
000
In lattice theory:
meet(A,B)means greatest lower bound.For bitmasks,
meet(A,B) = A & BbecauseAND gives lower bounds.A&B ≤ AandA&B ≤ B
Greatest Lower Bound: Any other mask
X, such thatX ≤ A, X ≤ Bmust satisfy:X ≤ A&B. ThusA&Bis the largest mask lying below both operands.
Boolean lattice explains:
AND Monotonicity: AND value moves downward in lattice.
Distinct subarray AND values: It remains small as down the lattice bits disappear.
Greedy pruning works: Branches below current states become constrained.
4.3 De Morgan's Laws
De Morgan's laws reveal a duality between AND and OR.
Statements involving AND can often be rewritten entirely in terms of OR, provided complements are introduced appropriately.
~(A ∧ B) = (~A) ∨ (~B)
Logical interpretation:
System Requirement: Power available ∧ Cooling operational
Failure Condition: ~(Power ∧ Cooling)
Equivalent to: (~Power) ∨ (~Cooling)
(Power failed OR Cooling failed)
Circuit Interpretation
Original Circuit:
NOT
|
AND
/ \
A B
Equivalent Circuit:
OR
/ \
~A ~B
De Morgan allows logic to be rewritten using different gate types.
4.4 Distributivity and Logical Forms
Distributivity allows conditions to be pushed inward or factored outward.
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
Logical interpretation:
Suppose:
A = User authenticated
B = Has read permission
C = Has write permission
A ∧ (B ∨ C): User is authenticated and has either read or write permission.
(A ∧ B) ∨ (A ∧ C): authenticated + read OR authenticated + write
Circuit interpretation:
Original circuit:
OR
/ \
B C
\ /
AND
|
A
Equivalent circuit:
OR
/ \
AND AND
/ \ / \
A B A C
Distributivity enables construction of:
Conjunctive Normal Form (CNF) AND of ORs
(A ∨ B) ∧ (C ∨ D)Disjunctive Normal Form (DNF) OR of ANDs:
(A ∧ B) ∨ (C ∧ D)
Distributivity allows: local conditions to be moved across global choices.
Behind every AND operation lies a simple question: What remains true for everyone? Understanding this perspective transforms AND from a bitwise operator into a powerful tool for reasoning about constraints, commonality, and information.
