Toggle all bits except after highest set bit

Viewed 353

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++??

3 Answers

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);

You can do something like this:

public static int toggle(int n) {
  int m = n;
  m |= m >>> 1;
  m |= m >>> 2;
  m |= m >>> 4;
  m |= m >>> 8;
  m |= m >>> 16;
  return n ^ m;
}

The repeated lines with powers of two, whose purpose is to set in m the most significant set bit of n and all bits less significant than it, can be replaced by a special instruction to find the number of leading zeros if you have access to such a thing.

The following implementations illustrate the efficient use of powers of 2 that David Eisenstat used but in languages which provide arbitrarily large integers, such as Python or Ruby. In other words, these solutions are not hardwired for 32 bit integers. I tested the Ruby version with inputs as large as 21000.

Ruby

def toggle(n)
  shift = 1
  m = n
  while (1 << shift) <= n
    m |= m >> shift
    shift <<= 1
  end
  m ^ n
end

Python

def toggle(n):
  shift = 1
  m = n
  while (1 << shift) <= n:
    m |= m >> shift
    shift <<= 1
  return m ^ n

You used the tag language-agnostic, so I'm taking you at your word even though you mention C++ and Java in your question.

Related