2

recently I was doing something related to bit manipulation. Up until now, I've tried many bit manipulations operations. But I am stuck at one operation.

Suppose I have int n = 5; binary (101), Now I would like to perform bitwise NOT on this int which I thought of the result would be (010) but rather the result was -6.

But when I tried n = ~(-n) it gave me the result 4 (Although still didn't get the right output). Please tell why is it showing this type of behaviour is it because my int is not unsigned. Also please tell me the perfect way to implement the operation so I can get the right output. My main motive is to flip the bits correctly.

Thank you

Vaibhav Bisht
  • 87
  • 2
  • 14
  • 1
    An `int` has more than 3 bits. One of them happens to be the sign-bit as you correctly guessed. What is _"the perfect way to implement the operation"_? Do you want to implement bitwise not yourself? What operation do you want to implement and what is not perfect now? – Lukas-T Jun 11 '20 at 07:01
  • 1
    Hint: `n = 5` contains a load of leading zeros (the number depends on the size of your `int`). You are setting those leading zeros to 1 in your output. – Bathsheba Jun 11 '20 at 07:01
  • @churill I just simply want to implement NOT operation like (101) -> (010) – Vaibhav Bisht Jun 11 '20 at 07:02
  • Correction: `int n = 5;` binary (0000000000000101) (at a minimum) – Guy Incognito Jun 11 '20 at 07:03
  • @GuyIncognito that much already know now. But how can I restrict the value of int up to a certain point? e .g. lets say I have 9 (1001) how can I restrict the size of int up to only first four digits and then implement the operation only to those – Vaibhav Bisht Jun 11 '20 at 07:07
  • 2
    You need to first find the most signficant set bit, construct a mask from that then do the negation and finally mask out the top bits. Your question is not clear and hence you are getting answers for exactly 3 bits which is probably not what you want. – kaylum Jun 11 '20 at 07:08
  • If `n` is 10, what result would you want? – Jabberwocky Jun 11 '20 at 07:12
  • 1
    @VaibhavBisht - You'll have to work out how many bits are set, and then only flip those bits. That's involves more than the `~` operator. You'll also need to be careful on handling the sign bit (elements of unspecified or implementation-defined [don't recall which offhand] behaviour on negative values). Also, unlike `~`, it means that applying your approach twice won't necessarily give back the original value (`101` -> `010` -> `001`). – Peter Jun 11 '20 at 07:13
  • @Jabberwocky if n = 10 (1010) then I would need to have the bits flipped i.e., (0101). – Vaibhav Bisht Jun 11 '20 at 07:16
  • @VaibhavBisht you should have specified this in your question. Peter's and kaylum's comments apply to your problem. – Jabberwocky Jun 11 '20 at 07:17
  • This can't be answered without knowing the type of `n`. The ~operator is notorious for screwing up the type of its operand, so if you use it with a signed integer or a small integer type, implicit type promotion will cause havoc. This sounds like the problem here to me. – Lundin Jun 11 '20 at 09:17
  • @Lundin "n" in here is of type unsigned int and also can you please tell me how ~operator would work in other cases (if int is signed int or long) – Vaibhav Bisht Jun 11 '20 at 09:25
  • @VaibhavBisht It would integer promote the operand, then set sign bits on signed positive numbers etc. https://stackoverflow.com/questions/46073295/implicit-type-promotion-rules – Lundin Jun 11 '20 at 09:27

3 Answers3

3

You probably want this:

// assuming n is a 32 bit int
n = 5;          // n = 00000000000000000000000000000101
n = ~n;         // n = 11111111111111111111111111111010
n = n & 0x7;    // n = 00000000000000000000000000000010

With the & operator (bitwise and) you mask the bits 3 to 31 of n

you can of course contract the two last statements into one:

n = ~n & 0x7;
Jabberwocky
  • 48,281
  • 17
  • 65
  • 115
3

int has more than tree bits, so you must mask the result of a bitwise negation like this:

int flip(int n) {
    // bitwise AND with 0b111 = 7, this will clear all but the last 3 bits
    return ~n & 0b111;
}

The reason you got -6 is because int is typically represented in two's complement, where -6 is all 1-bits but ends with 010. You must remove these leading 1-bits to get the correct result.

Generally, I would recommend not using bitwise operations with signed numbers and instead do the following:

unsigned flip(unsigned n) {
    return ~n & 0b111;
}

// this version works with any number of bits, not just 3
unsigned flip(unsigned n, unsigned bits) {
    unsigned mask = (1 << bits) - 1;
    return ~n & mask;
}

If you don't know how many bits your number has, you must first find the most significant bit. In the most naive way, it can be done like this:

unsigned log2(unsigned val)
{
    unsigned result = 0;
    while (val >>= 1) {
        ++result;
    }
    return result;
}

unsigned variable_flip(unsigned n) {
    return flip(n, log2(n));
}

You can find more efficient solutions here.

For example:

unsigned log2_debruijn(uint32_t val) {
    static const unsigned MultiplyDeBruijnBitPosition[32] = {0, 9,  1,  10, 13, 21, 2,  29, 11, 14, 16, 18, 22, 25, 3, 30,
                                                          8, 12, 20, 28, 15, 17, 24, 7,  19, 27, 23, 6,  26, 5,  4, 31};

    // first round down to one less than a power of 2
    // this step is not necessary if val is a power of 2
    val |= val >> 1;
    val |= val >> 2;
    val |= val >> 4;
    val |= val >> 8;
    val |= val >> 16;

    return MultiplyDeBruijnBitPosition[(val * uint32_t{0x07C4ACDD}) >> 27];
}
Jan Schultke
  • 17,446
  • 6
  • 47
  • 96
  • what is 0b111 it's not a hexadecimal value. What is it? And why are performing AND(&) operation with it?? – Vaibhav Bisht Jun 11 '20 at 07:14
  • 2
    @VaibhavBisht `0b111` is a binary value, it's the same as `0x7` which is hexadecimal or `7` which is decimal. – Jabberwocky Jun 11 '20 at 07:16
  • @Jabberwocky but why are we only performing and (&) operation with 7 – Vaibhav Bisht Jun 11 '20 at 07:18
  • 3
    @VaibhavBisht Because you did not make it clear in your question that you want a general algorithm to handle variable bit widths. – kaylum Jun 11 '20 at 07:20
  • @VaibhavBisht because the number 5 has 3 significant bits. This arrticle might be interesting for you: https://stackoverflow.com/questions/31393100/how-to-get-position-of-right-most-set-bit-in-c – Jabberwocky Jun 11 '20 at 07:21
  • @VaibhavBisht 0b111 is non-standard goo that won't compile on your standard C compiler. So this answer isn't particularly helpful. – Lundin Jun 11 '20 at 09:18
  • @Lundin the question is tagged C++ and `0b` is a standardized prefix since C++14. GCC also supports binary literals. – Jan Schultke Jun 11 '20 at 09:26
  • @kaylum how can I find the variable bits in the above code. – Vaibhav Bisht Jun 11 '20 at 09:28
  • @J.Schultke Yikes, yet another of them "C/C++" fiascos then. – Lundin Jun 11 '20 at 09:28
  • @VaibhavBisht I updated the question to include a solution for that problem. – Jan Schultke Jun 11 '20 at 09:33
  • @J.Schultke I know I can find bits by numberOfBits = floor(log2(x)) + 1; or unsigned bits, var = (x < 0) ? -x : x; for(bits = 0; var != 0; ++bits) var >>= 1; is there any other efficient way to do it – Vaibhav Bisht Jun 11 '20 at 09:35
  • @VaibhavBisht I updated the question again. You can follow the link for various solutions, this efficient implementation will work for anything up to 32 bit integers. – Jan Schultke Jun 11 '20 at 09:39
2

First you need to find the most significant bit. You can do this by shifting right by 1 until you hit zero, counting how many times you shift.

unsigned int bit = 0;
unsigned int tmp = n;
while (tmp) {
    tmp >>= 1;
    bit++;

Then shift the value 1 right that many bits, giving you a value of n rounded up to the nearest power of 2, then subtract 1 to get a mask with all bits below that value set:

unsigned int mask = (1U << bit) - 1;

Then XOR it with your value to flip the bits set in the mask:

n = n ^ mask;
dbush
  • 205,898
  • 23
  • 218
  • 273