Bitwise Greedy

May 2026 · 24 min read

Bitwise greedy builds an answer from the most significant bit down. Because a higher bit dominates every lower bit combined, you can often try to set a candidate bit, test feasibility, and keep it if possible.

MSB-to-LSB Template

int ans = 0;
for (int b = LOG; b >= 0; --b) {
    int candidate = ans | (1 << b);
    if (feasible(candidate)) ans = candidate;
}

The hard part is designing feasible. It should answer: "Can the final answer have at least these bits?"

Maximum AND

To maximize the AND of a chosen group, try bits from high to low and keep only numbers that contain the candidate mask.

int max_and_pair(vector<int>& a) {
    int ans = 0;
    for (int b = 30; b >= 0; --b) {
        int cand = ans | (1 << b);
        int cnt = 0;
        for (int x : a) if ((x & cand) == cand) ++cnt;
        if (cnt >= 2) ans = cand;
    }
    return ans;
}

Maximum XOR

For maximum XOR pair, the set-prefix method tries to force each answer bit to 1.

int findMaximumXOR(vector<int>& nums) {
    int ans = 0, mask = 0;
    for (int b = 30; b >= 0; --b) {
        mask |= 1 << b;
        unordered_set<int> pref;
        for (int x : nums) pref.insert(x & mask);
        int cand = ans | (1 << b);
        for (int p : pref) {
            if (pref.count(p ^ cand)) {
                ans = cand;
                break;
            }
        }
    }
    return ans;
}

Constructive Bit Problems

When asked to build values satisfying AND/OR/XOR constraints, reason per bit. Each bit is often independent unless there is a carry, sum, or ordering constraint.

• AND requires all selected values to have 1.
• OR requires at least one selected value to have 1.
• XOR requires odd parity of 1s.

Pitfalls

• Greedy by bit is valid only when feasibility is monotonic.
• Try high bits first; low bits cannot compensate for a lost high bit.
• If arithmetic carries are involved, bits are no longer independent.

Practice Problems

• LeetCode 421 - Maximum XOR of Two Numbers MSB greedy prefix feasibility.
• LeetCode 2275 - Largest Combination With Bitwise AND Greater Than Zero bit counts choose best bit.
• LeetCode 2419 - Longest Subarray With Maximum Bitwise AND AND property maximum AND requires max elements.
• Codeforces 1556D - Take a Guess bit reconstruction recover values from AND/OR sums.