2

Given a binary integer, how can I invert (flip) last n bits using only bitwise operations in c/c++?
For example:

// flip last 2 bits
0110 -> 0101
0011 -> 0000
1000 -> 1011
MuhsinFatih
  • 1,891
  • 2
  • 24
  • 31
  • @paulsm4: I think you will find it's not that simple. – TonyK Jan 05 '19 at 23:53
  • @paulsm4 notice I said **last n bits**, not the whole number, which is not as trivial – MuhsinFatih Jan 05 '19 at 23:54
  • OK, now it is clearer. But what have you tried so far ? – Christophe Jan 05 '19 at 23:57
  • 1
    @harold I updated the title and the question to clarify the intention. Thanks for pointing out – MuhsinFatih Jan 05 '19 at 23:57
  • 2
    In that case we have [set n bits](https://stackoverflow.com/q/45352352/555045) and XOR by that mask – harold Jan 05 '19 at 23:58
  • @Christophe I tried a bunch of different bitwise expressions but they were very spagetti so I thought if wouldn't be useful to include in the question – MuhsinFatih Jan 05 '19 at 23:59
  • @BenVoigt I've updated the question to include more examples – MuhsinFatih Jan 06 '19 at 00:02
  • @paulsm4 Thanks for pointing out that the question was not clear. I am familiar with XOR but the challenge was to flip the last n bits rather than the whole thing. I added more examples and hopefully the question is more clear now. I wanted to add example code but what I tried was too spagetti and wasn't really helpful so I assumed keeping the question shorter would be more useful. One of my attempts for example: `(u << n) + ~(u & ~(~0U << n))`, which is pretty overkill for this problem – MuhsinFatih Jan 06 '19 at 00:18

1 Answers1

6

You can flip last n bits of your number with

#define flipBits(n,b) ((n)^((1u<<(b))-1))

for example flipBits(0x32, 4) will flip the last 4 bits and result will be 0x3d

this works because if you think how XOR works

 0 ^ 0 => 0
 1 ^ 0 => 1

bits aren't flipped

0 ^ 1 => 1
1 ^ 1 => 0

bits are flipped

 (1<<b)-1

this part gets you the last n bits for example, if b is 4 then 1<<4 is 0b10000 and if we remove 1 we get our mask which is 0b1111 then we can use this to xor with our number to get the desired output.

works for C and C++

MuhsinFatih
  • 1,891
  • 2
  • 24
  • 31
Mehmet Emin Kartal
  • 177
  • 10
  • 4
    Could be an acceptable answer if you would put the define expression between parenthesis, in order to avoid issues with preprocessing an priority. Would be much better with an inline function or a template function. – Christophe Jan 05 '19 at 23:55
  • I think OP wants to reverse those bits, not flip them. @MuhsinFatih, can you give a more helpful example? `0110 -> 0101` can be interpreted as reversing or flipping. – TonyK Jan 05 '19 at 23:55
  • 5
    The behavior of `1< – Eric Postpischil Jan 06 '19 at 00:06
  • @TonyK I meant flip, updated the question to clarify the intent. Although I am curious, I don't understand the grammar here. How is reverse different than flip? Your example is valid for flipping too – MuhsinFatih Jan 06 '19 at 00:06
  • 1
    @MuhsinFatih: reversing all the bits of e.g. `11101001` gives `10010111`. It means writing the bit string backwards. – TonyK Jan 06 '19 at 00:18
  • 1
    Better now :-) But have you tried `flipBits(0x32,6&5)` which should give the same result than your example since 6&5 is 4? With define, you need also parenthesis around each parameter you use, since define works with dumb substitution. Demo https://ideone.com/qHefN5 – Christophe Jan 06 '19 at 00:19
  • @TonyK oh that makes sense :) – MuhsinFatih Jan 06 '19 at 00:21
  • I don't know how the answer gets + votes. Seemingly everybody rules overflow bug out. – Soner from The Ottoman Empire Jan 06 '19 at 02:20
  • 1
    using macros is a bad idea if you don't know how it works [The need for parentheses in macros in C](https://stackoverflow.com/q/10820340/995714) – phuclv Jan 06 '19 at 02:23
  • 2
    Better to use `1u<<(b)` than `1<<(b)` – chux - Reinstate Monica Jan 06 '19 at 02:42
  • `flipBits(n,b)` fails when `n` is wider than `int/unsigned`. – chux - Reinstate Monica Jan 06 '19 at 02:43
  • If you use a macro, make it more generic and handle the largest type: `#define flipBits(n, b) ((n) ^ ((1ULL << (b)) - 1))` – chqrlie Jan 06 '19 at 15:38