How to get the bitwise not of a number but do not negate the sign bits?

Question

I have a number that is representing a mask and I want to get the negative mask (0110, that is 6). I thought to do the bitwise not but it seems that it negate also the sign bit, and I get an unwanted value...

size_t msk = 9; // that is 1001, or 000...01001 on more bits
size_t nMsk = ~msk; // this I want to be 6, that is 0110, but bitwise not  
                    // is negating all the bits, so I get 111...10110

Is there a fast way to do it (without a loop)?

EDIT More info:

I have added some better case in some comment of one of the answer: In my case, 16 is 100000000 and ~16 is not 111011111111, but 000011111111

What is this for? Are you sure this is the problem? Usually when people want something like this, it turns out they were distracted by the extra set bits and turns out they're not a problem. If you're working with 4-bit numbers, that'll be simple: `nMsk = msk ^ 15` — harold, May 24 '16 at 13:02
No, I am working with larger numbers, but it was easy to show it on 4 bits :) sorry — sop, May 24 '16 at 13:06
The only way to do this is to XOR with a value set to 1's, up to [the highest bit in your input](http://stackoverflow.com/questions/4801207/what-is-the-most-portable-way-to-get-set-highest-bit-of-an-integer-in-gnu-c). — Jongware, May 24 '16 at 13:06
Ok, how big then? Or do you want to complement up to and including the highest set bit? (which is a weird thing to want btw) — harold, May 24 '16 at 13:07
`size_t` is **unsigned**! Thus it has no sign-bit by definition. Your question is not clear. — too honest for this site, May 24 '16 at 13:10
@sop: No, it is not. This might be an XY-problem. What is your **actual** problem behind the proposed "solution"? — too honest for this site, May 24 '16 at 13:14
@sop - Are the numbers always the same length in bits? If so, how many? — owacoder, May 24 '16 at 13:16
it seems that what you want to do is turn off specific bits. a simple `and` will do that nicely. Example if want to turn off bits 1 and 2 in a byte (bits start with 0) you can use: `char var = 0xff; var &= ~0x06;` — user3629249, May 25 '16 at 07:08

score 6 · Accepted Answer · answered May 24 '16 at 13:02

6

If you want your value to be 6 as you asked, then you need to remove all the bits in front of it that you are not using.

size_t nMsk = (~msk) & 0xF;

Masking it with 0xF, which is equal to 1111 in binary will remove all the bits except for the last 4, resulting in your desired value.

answered May 24 '16 at 13:02

Rick de Water

2,388
3
19
37

This answer is pretty good, but if I do not know the number of bits the mask is using, how do I do? – sop May 24 '16 at 13:34
@sop At this point I think you need to tell us why you want to do this, because this seems like an odd thing to do in the first place. – Rick de Water May 24 '16 at 13:38

score 3 · Answer 2 · answered May 24 '16 at 13:21

3

OP states in one comment that he does not know the number of bits in advance. One way to solve this is to use a lookup table. An 8-bit example of this is

uint8_t lookup[] = { 0, 1, 3, 7, 15, 31, 63, 127, 255 };
result ^= lookup [numberofbits];

answered May 24 '16 at 13:21

Weather Vane

33,872
7
36
56

Except the OP still needs to find the number of bits in the number, which likely requires a loop. – owacoder May 24 '16 at 13:29

score 2 · Answer 3 · answered May 24 '16 at 13:39

2

If you make an assumption about the maximum number of bits you're working with, you can get a mask of "all bits at or below the highest set bit" without too much magic (though magic may be faster)

size_t m = msk;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
m |= m >> 32; // if size_t is more than 32 bits

Then just XOR with that:

nMsk = msk ^ m;

This is an unusual operation though, I still suspect you really meant something else.

answered May 24 '16 at 13:39

harold

61,398
6
86
164

1

True it is not a loop, it is an unrolled loop. – Weather Vane May 24 '16 at 13:43
Yes, in the end I used a loop, but I thought that there may be a much simpler way to do it, I think it is ok with the loop – sop May 24 '16 at 13:45

score 1 · Answer 4 · answered May 24 '16 at 13:08

1

the signbit is just inverted, since the ~ does not take signed/unsigned into account. Example:

uint8_t a = 54; /*     0011 0110 */
uint8_t b = ~a; /* 201 1100 1001 */

int8_t c = 54; /*      0011 0110 */
int8_t d = ~c; /* -55  1100 1001 */

If you only want to invert some of the bits, you can use xor instead, example:

uint8_t a = 54;     /*     0011 0110 */
uint8_t b = a ^ 15; /* 57  0011 1001 */

answered May 24 '16 at 13:08

Stian Skjelstad

2,277
1
9
19

I also tested the idea but it seems that I shall know the number of bits the mask is using, but I am not sure that this is fixed... that is why I am asking for something that knows to remove the 1s form my number – sop May 24 '16 at 13:12
What exactly is your use-case? – Stian Skjelstad May 24 '16 at 13:33
my case is 0x1b7, and what I expect is 0x48, but I would like it to work also for 0x10 (that is returning 0xF) – sop May 24 '16 at 13:36

jweyrich · Answer 5 · 2016-05-30T12:43:08.680

Here's my attempt (see the output):

#include <climits>
#include <cmath>
#include <bitset>
#include <iostream>

template <typename T>
T build_mask(T num) {
    const int up_to_bit = ceil(log2(num));
    for (int i = 0; i < up_to_bit; i++)
        num |= 1 << i;
    return num;
}

template <typename T>
std::bitset<sizeof(T) * CHAR_BIT> get_bits(T num) {
    return std::bitset<sizeof(T) * CHAR_BIT>(num);
}

int main() {
    int32_t msk = 9;
    int32_t nMsk = ~msk & build_mask(msk);

    std::cout << "value: " << msk << std::endl;
    std::cout << "bits : " << get_bits(msk) << std::endl;
    std::cout << "mask : " << get_bits(build_mask(msk)) << std::endl;

    std::cout << "value: " << nMsk << std::endl;
    std::cout << "bits : " << get_bits(nMsk) << std::endl;

    return 0;
}

score 0 · Answer 6 · edited May 24 '16 at 13:45

0

How about preserving the sign bit via bitwise xor:

size_t nMsk = ~msk ^ (1 << ((sizeof(size_t) * CHAR_BIT) - 1));

It will first invert the mask and then toggle the sign bit.

edited May 24 '16 at 13:45

joelw

401
3
11

answered May 24 '16 at 13:17

bricklore

4,125
1
34
62

Thats the clue, it gets shifted it to the position of the signbit – bricklore May 24 '16 at 13:19
For a 4-byte `size_t`, the shift will be `1 << (4-2)`, not the expected `1 << (32 - 1)`. (Assuming the system has 8-bit bytes) – owacoder May 24 '16 at 13:21
Sorry you were completely right, I think I wasnt fully awake when I answered you ;) – bricklore May 24 '16 at 13:23
Ok, with "sign bit" I meant the 1s that are in front of the mask on x bits (eg 16 is 100000000 and ~16 is not 111000000000, but 000011111111 in my case) – sop May 24 '16 at 13:23

How to get the bitwise not of a number but do not negate the sign bits?

6 Answers6