C++ NOT outputing... +1 negative

Question

How do i make program which outputs NOT(x)?

Example:

12 to 3
0 to 1
2 to 1

explained:

1100 to 0011
0 to 1
01 to 10

printf("%i\n%i\n%i\n", ~12, ~0, ~2);

Prints:

-13
-1
-3

printf("%i\n%i\n%i\n", !12, !0, !2);

Prints:

0
1
0

Tell me, why `NOT(0)` is `1` in your example, yet `NOT(1)` is `10`? How should we know that `1` is actually `01`, and not `000001`? — raina77ow, Nov 02 '12 at 15:05
NOT(1) = 0... 10 is binary, in decimal = 1. 1 is not 01 neither 00001, it is just 1, and NOT(1) = 0. — user1794604, Nov 02 '12 at 15:07
@user1794604 You should also take into account that `12`, represented as, say, a 1-byte integer, isn't `1100`, but `00001100`. Flipping all bits yields `11110011`. — jogojapan, Nov 02 '12 at 15:08
@jogojapan So how do I achieve what I'm asking for? For 000010010010, not should consider only 10010010, zeroes before the first 1 are not to be considered. — user1794604, Nov 02 '12 at 15:11
There is an existing question on how to find the most significant 1-bit (i.e. the left-most 1, which is what you need): http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i oh and now Dan Puzey described it all in his post. Combine the msb (most-significant bit) search of my link with the steps of his answer. — jogojapan, Nov 02 '12 at 15:22

score 5 · Answer 1 · edited May 23 '17 at 10:25

Your variadic arguments to printf are being promoted to int, Think of it as storing your bits in variables first (int), then performing the bit-not on them:

int x = 12;     // 0x0000000C
int y = ~x;     // 0xFFFFFFF4

y is now a negative signed int value.

Change your format string and your values to unsigned and it may be closer to what you're looking for:

int main(int argc, char *argv[])
{
    unsigned int x = 12;
    unsigned int y = ~x;
    printf("%u:%u\n",x,y);
    return EXIT_SUCCESS;
}

Results:

12:4294967283

If you're looking for functionality to print actual "bit-ness" of the values an excellent starting point can be found here, since printf() has no native bit-binary print capabilities.

Finally, if all you're interested in flipping is the leading most significant non-zero bits be sure to special-condition your case when the input value is zero (0). You really need a "this many bits are significant to me" value to really do this right.

EDIT: A Tremendously Inefficient BitString: Obviously this will NOT work without a numeric type for the lead template argument. Use at your own discretion (and peril).

template<typename T, size_t N=sizeof(T)*8>
std::string bit_string(T value, size_t maxbits=N)
{
    static const char *one = "1";
    static const char *zero = "0";
    std::string result;

    maxbits = std::min(maxbits, N);
    for (size_t i=0;i<maxbits;i++)
    {
        result = ((value & T(1)) ? one : zero) + result;
        value >>= 1;
    }
    return result;
}

Dan Puzey · Answer 2 · 2012-11-02T15:21:29.490

Your first example works the way it does because of the two's complement binary notation for negative numbers.

For example, the value 12 will actually be represented as 0000000000001100 in a 16-bit integer, and most likely will actually be a 32-bit integer. A bitwise-not of this value is 1111111111110011, and this is -13 in two's complement.

Your second sample code uses a boolean-not operator. C++ treats any non-zero value as true, and the value of "not true" is always false, or the integer 0. Similarly, the !0 means "not false" and will return -1 as C++'s "standard true" value. (This value is used because !0 == -1 in two's complement, and so !false and ~false are equivalent operations.)

So: what you are proposing to do is more complicated than you think. What you call "NOT(x)" is actually "the bitwise NOT of a binary number, truncated to the smallest number of significant digits, and interpreted as unsigned." That's not as simple as you make it sound!

The significant digits part is especially important. If all numbers are 8-bit unsigned, then "NOT(2)" is actually 253 not (as you say you require) 1.

It's also interesting to note that your definition means that NOT is no longer reversible: NOT(NOT(12)) is not 12, but would in fact NOT(12) = 3 and then NOT(3) =0.

So, in order to implement what you want:

Work out what the most significant digit of your original number is (which is the highest power of 2 that is less than your original number?). (Represent this value as sd for later.)
Bitwise-invert your original number
Bitwise-AND the result with 2 ^ (sd) - 1

For example, with the number 12:

most significant digit is 4 ( 2 ^ 4 = 16)
inverted number (assuming 16-bit) is 1111111111110011
2 ^ 4 - 1 = 15 which in binary is 0000000000001111
1111111111110011 AND 0000000000001111 == 0000000000000011 which is the result you wanted.

So basically what you're saying, I have to write my own function which takes 1's and 0's, removes all 0's before the first 1 (000100 -> 100) and inverts them? — user1794604, Nov 02 '12 at 15:16
It can be done a bit easier, if you remember that all the unneeded 0 will be converted to 1 in inversion. Basically, you need to take all that follows the first `0` (when counting from left to right) encountered in the result of inversion. — raina77ow, Nov 02 '12 at 15:19
Yes, basically - or find an alternative way of finding the same result (such as what @raina77ow suggests). What you've described isn't a simple operation, so the solution isn't as simple as a single operation. — Dan Puzey, Nov 02 '12 at 15:27

score 0 · Answer 3 · answered Nov 02 '12 at 15:11

0

Well, if you want to flip all of the bits in an int, you could subtract the value from int max, or to flip a short, subtract from short max... at least I think that's what you're asking.

answered Nov 02 '12 at 15:11

Sev08

76
7

C++ NOT outputing... +1 negative

3 Answers3