CODEWITHSUNDEEP
c++logicbit-manipulation
Coolwater
Coolwater

Reputation: 723

How to implement this bitwise manipulation?

I have an integral type with some value. E.g. say some int foo has the bit representation:

11011001101101011010101000001111

I need a function f that manipulates it as follows: Prepending a 0 makes it

011011001101101011010101000001111 (*)

To obtain the final value I need, the following bit sequence is made, which has ones whenever successive bits of (*) are unequal.

10110101011011110111111100001000

which is f(foo)

How should this be implemented in c++?

Upvotes: 2

Views: 75

Answers (1)

alexeykuzmin0
alexeykuzmin0

Reputation: 6440

Short: solution is

unsigned f(unsigned x)
{
  return x ^ (x >> 1U);
}

Brief explanation:

You need to bitwise compare some numbers, having 1 if the bits differ, and 0 otherwise. That's exactly what the ^ operation does.

Further, you need to compare i-th bit of the number with (i+1)-st (and 31-st bit with 0), but ^ compares i-th bits of some numbers. So, we should transform the number in such a way that it will have bit from (i+1)-st place on i-th place, and add 0 in the very beginning. That's what exactly >> operation does.

Also, please mention that

int f(int x)
{
  return x ^ (x >> 1);
}

will not work correctly for all cases, since negative int numbers (all numbers starting with 1), will get 1 at the beginning when being shifted right.

Upvotes: 4

Related Questions