Keep Only the Highest Set Bit

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

// Complete the function
uint16_t highest_set_bit(uint16_t reg) {
    // Your logic here
    // Walk from the highest bit (15) down to the lowest (0)
    for (int i = 15; i >= 0; i--) {
        
        // Use our "Detector" to check if this bit is ON
        if (reg & (1 << i)) {
            
            // We found the first ON switch! 
            // Return a value where ONLY this bit is ON.
            return (1 << i); 
        }
    }
    
    // If the loop finishes and we never found an ON bit, 
    // the original number must have been 0.
    return 0;

}

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

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

When you see a new bitwise problem, the best approach is to step back from the code and map it out using plain English and our light switches analogy.

Here is how an experienced programmer thinks through the "Highest Set Bit" problem.

Phase 1: Translate to Plain English

The Problem: "Keep only the highest (leftmost) set bit in a 16-bit register. Clear all others."

The Translation: "I have a row of 16 light switches. Some are ON, some are OFF. I want to walk down the row, find the very first switch that is ON (starting from the highest value on the left), and return a new row where only that one switch is ON."

Phase 2: Choose the Direction

If we want the highest (leftmost) switch, where should we start looking?

• If we start from the right (Index 0), we might find a switch that is ON, but we won't know if there's a higher one further down the line unless we keep checking.
• Logical Choice: We must start scanning from the left (Index 15) and walk down to the right (Index 0). The first switch we find that is ON is guaranteed to be the highest one!

Phase 3: Check Your Toolkit

We need to do two things:

1. Check if a switch is ON. (We know how to do this: reg & (1 << i)).
2. Create a result where only that switch is ON. (We know how to do this too: (1 << i) creates exactly that mask!).

Phase 4: Draft the Logic (Mental Walkthrough)

Let's imagine our number is 18. In 16-bit binary: 0000 0000 0001 0010 (The switches at Index 4 and Index 1 are ON).

1. Look at Index 15. Is it ON? No.
2. Look at Index 14. Is it ON? No. ... fast forward ...
3. Look at Index 4. Is it ON? YES!
4. Stop looking! We found the highest bit.
5. We want to return a number where only Index 4 is ON. That number is simply (1 << 4), which is 16.

We don't even need to write code to "turn off" the other bits. By just returning (1 << 4), we are instantly generating a brand new, clean row of switches where only that one switch is flipped!

Phase 5: Write the Code

Now, we just translate our mental walkthrough into a simple C loop:

#include <stdint.h>

uint16_t keep_highest_bit(uint16_t reg) {
    // Walk from the highest switch (15) down to the lowest (0)
    for (int i = 15; i >= 0; i--) {
        
        // Use our "Detector" to check if this switch is ON
        if (reg & (1 << i)) {
            
            // We found the first ON switch! 
            // Return a value where ONLY this switch is ON.
            return (1 << i); 
        }
    }
    
    // If the loop finishes and we never found an ON switch, 
    // the original number must have been 0.
    return 0;
}

The Takeaway

When you see a new bitwise problem, the best approach is to step back from the code and map it out using plain English and our light switches analogy.

Here is how an experienced programmer thinks through the "Highest Set Bit" problem.

Phase 1: Translate to Plain English

The Problem: "Keep only the highest (leftmost) set bit in a 16-bit register. Clear all others."

The Translation: "I have a row of 16 light switches. Some are ON, some are OFF. I want to walk down the row, find the very first switch that is ON (starting from the highest value on the left), and return a new row where only that one switch is ON."

Phase 2: Choose the Direction

If we want the highest (leftmost) switch, where should we start looking?

• If we start from the right (Index 0), we might find a switch that is ON, but we won't know if there's a higher one further down the line unless we keep checking.
• Logical Choice: We must start scanning from the left (Index 15) and walk down to the right (Index 0). The first switch we find that is ON is guaranteed to be the highest one!

Phase 3: Check Your Toolkit

We need to do two things:

1. Check if a switch is ON. (We know how to do this: reg & (1 << i)).
2. Create a result where only that switch is ON. (We know how to do this too: (1 << i) creates exactly that mask!).

Phase 4: Draft the Logic (Mental Walkthrough)

Let's imagine our number is 18. In 16-bit binary: 0000 0000 0001 0010 (The switches at Index 4 and Index 1 are ON).

1. Look at Index 15. Is it ON? No.
2. Look at Index 14. Is it ON? No. ... fast forward ...
3. Look at Index 4. Is it ON? YES!
4. Stop looking! We found the highest bit.
5. We want to return a number where only Index 4 is ON. That number is simply (1 << 4), which is 16.

We don't even need to write code to "turn off" the other bits. By just returning (1 << 4), we are instantly generating a brand new, clean row of switches where only that one switch is flipped!

Phase 5: Write the Code

Now, we just translate our mental walkthrough into a simple C loop:
When faced with a bitwise problem:
 

Summarily:

1. Visualize the switches. 2. Decide how to iterate (Left-to-right? Right-to-left? Or acting on all of them at once?).
2. Use your basic tools (Set |, Clear & ~, Toggle ^, Check &) to build the solution.

Pro-Tip: Because you just wanted to keep one bit, you didn't have to clear the others manually. Returning a brand new mask (1 << i) was a logical shortcut!