Keep Only the Highest Set Bit

Code

#include <stdio.h>
#include <stdint.h>

// Complete the function
uint16_t highest_set_bit(uint16_t reg) {
    if(reg==0){
        return 0;
    }

    reg|=reg>>1;
    reg|=reg>>2;
    reg|=reg>>4;
    reg|=reg>>8;

    return (reg+1) >>1;
}

int main() {
    uint16_t reg;
    scanf("%hu", &reg);

    uint16_t result = highest_set_bit(reg);
    printf("%hu", result);
    return 0;
}

Solving Approach

✅ Keep Only the Highest Set Bit

Given a 16-bit number:

• Keep only the highest (leftmost) set bit
• Clear all other bits
• Return 0 if input is 0

🧠 Core Idea

We solve it in 2 logical phases:

1️⃣ Spread highest bit downward
2️⃣ Isolate the highest bit

🔹 Step 1 — Handle Zero Case

if (reg == 0)
    return 0;

Because 0 has no set bits.

🔹 Step 2 — Bit Spreading (Propagation)

reg |= reg >> 1;
reg |= reg >> 2;
reg |= reg >> 4;
reg |= reg >> 8;

What this does:

Each shift + OR operation spreads the highest 1 toward the right.

Example:

Input:

0000000000101100   (44)

After spreading:

0000000000111111

Now all bits from highest set bit down to LSB become 1.

Why shifts 1,2,4,8?

Because for 16-bit numbers:

Together they ensure full coverage in log₂(16) steps.

🔹 Step 3 — Isolate Highest Bit

return (reg + 1) >> 1;

Why this works:

If after spreading:

0000000000111111

Add 1:

0000000001000000

Shift right:

0000000000100000

✔ Only highest bit remains.

✅ Final Logic Summary

1. Spread highest bit to the right
2. Convert 111... form into pure power of two
3. Return that value

📌 Final Compact Code

uint16_t highest_set_bit(uint16_t reg) {
    if (!reg) return 0;

    reg |= reg >> 1;
    reg |= reg >> 2;
    reg |= reg >> 4;
    reg |= reg >> 8;

    return (reg + 1) >> 1;
}

🚀 Why This Is Powerful

✔ No loops
✔ No branching (except zero check)
✔ Constant time
✔ Works for any 16-bit value
✔ Frequently asked in interviews