Toggle all bits except after highest set bit

Question

How can I toggle all bits of a number except after the highest set bit?

For Example: Let's suppose a 32-bit number that needs to be toggled.

00000000000000000010011110000100  // Input

00000000000000000001100001111011  // Expected

How could I achieve this in a java/C++??

Answer 1

We can do the follow. For given n = 10011110000100

1. We'll find the smallest power of 2 v = 100...00 such that v > n.
2. Then result = n ^ (v - 1) (note that b XOR 1 toggles bit b)

What's going on:

n           =  10011110000100
v           = 100000000000000
v - 1       =  11111111111111
n ^ (v - 1) =  01100001111011

Code:

int n = 0b10011110000100;

int v = 1;

while (v <= n)
  v <<= 1;

int result = n ^ (v - 1);