CODEWITHSUNDEEP
javascriptbit-manipulation
user2020493
user2020493

Reputation: 129

Could anyone please explain what the following code does and HOW it works?

My teacher said it was javascript if that helps

function mystery(x) { 
  x--; 
  x|= x>> 1; 
  x|= x>> 2; 
  x|= x>> 4;
  x|= x>> 8; 
  x|= x>> 16; 
  x++; 
  return x; 
}

Upvotes: 0

Views: 117

Answers (3)

recursion.ninja
recursion.ninja

Reputation: 5488

The function mystery(x), gets the next highest power of 2 of a number x. The initial decrement statement (x--) makes the function returns the same value if the number is already a power of 2. mystery(x) will behave interestingly for signed integers when approaching INT_MAX_VALUE.

You could have derive this answer by graphing the function values for small values of x

Upvotes: 1

Amadan
Amadan

Reputation: 198334

It finds the lowest power of two that is greater or equal to x. Alternately, everything after x-- will find the lowest bit that is left of all the ones in x-1.

For example, if you have x - 1 as

00010100111010100001010011101010

then mystery(x) will be

00100000000000000000000000000000

It first fills up all the zeroes that follow a one, by folding the ones to the right; after the first operation, every one will have one following it. Then we fold two-bit groups: every two ones will now become four. Then we fold four, then eight. Then we take out the big hammer, sixteen bits.

00010100111010100001000000001100  // x - 1
00011110111111110001100000001110  // after folding one bit
00011111111111111101111000001111  // after 2
00011111111111111111111111101111  // after 4
00011111111111111111111111111111  // after 8, and every step thereafter

Here, x++ will switch all ones to zero, making one carry to the next column:

00100000000000000000000000000000  // after x++

The weird decrement at the start is so we catch <= instead of strict <. For example, if we start with

00000000000000000000000000000100  // x
00000000000000000000000000000011  // after x--
00000000000000000000000000000011  // after folding, unchanged - they're all ones anyway
00000000000000000000000000000100  // after x++

Upvotes: 3

TheWhiteRabbit
TheWhiteRabbit

Reputation: 15758

The statement 

x>> 1;
  • Shifts x in binary representation 1 bits to the right, discarding bits shifted off

x|= x>> 1;

  • Performs a bitwise OR on the result of x >> 1 with x and stores the result in x

Upvotes: 1

Related Questions