Negate every bit value of a binary in C

Question

So I got a coding problem, the the program asks me to negate every bit of a binary, for example, the regular bitwise negation will be like this: ten = 00001010 the negation is 11110101 = 245, well to achieve this, in my opinion, I can just XOR it with 255.

But the real problem is they only ask to negation only until the last '1'. My teacher teaches me to read binary from right so the last '1' if the number is ten is 2^3.

So ten = 1010 the bitwise negation is 0101 = 5

another example is

5 = 00000101 -> take only until the last '1' which is 2^2

so its like ignore this ->[00000], and only use this ->[101]

so now 5 = 101 the negation will be '010' which is equal to 2

I wonder if is there any method to help me achieve this result, at first I thought about using a loop like:

for(int i = 7; i >= 0;i--)

And store the index to a char to represent the binary and try to negate it from there, but I quickly stop when I see the constraint is 0 < n <= 1000000

How can I solve this problem?

Answer 1

What you call "last" bit is usually called "most significant bit" — less confusion with this name.

1. Find the most significant bit using any of several known techniques.

2. From that, create a mask which has 1 for all bits you want to flip and 0 for all other bits.

3. Use XOR with this mask.

Answer 2

It could be something like this, but if you demonstrate this solution written on my phone, not tested, to your teacher, it will guess that this is not your own solution

unsigned int x;
if (scanf("%u", &x) == 1) {
  int bits;
  frexp(x, &bits);
  x = x ^ ((1ULL << bits) - 1);
  printf("%u\n", x);
}

Answer 3

#include <stdio.h>

int main() {
    unsigned input = 10;
    unsigned mask = 1u << 8*sizeof(input)-1; // most significant bit is always 1, no matter the variable type
    unsigned result = 0;
    
    while ( (input & mask) == 0) mask>>=1; // looking for first 1

    // >> puts 1 in front ( 1000 -> 1100 ) instead of ( 1000 -> 0100 )
    //    if most significant bit is 1
    mask &= input; // getting rid of all extra bits
    while (mask > 0) {
        result |= (input & mask) ^ mask;
        mask>>=1;
    }
    printf("Input: %u\nOutput: %u\n", input, result);
    return 0;
}

Answer 4

In your example, you want to negate the bits for 1010₂. You suggest you could obtain the result you want with n ^ 0b1111. As this implies, XORing with zero has no effect, and XORing with one negates.

x	y	x ^ y	x ^ y
0	0	0	x
1	0	1	x
0	1	1	~x
1	1	0	~x

This means n ^ 0b1111 is equivalent to n ^ 0b1 ^ 0b10 ^ 0b100 ^ 0b1000. That presents a simple solution that works for any unsigned integer type as long as we can loop the correct number of times.

To determine the number of times to loop, we just need to repeatedly shift.

10102	Not zero: Enter loop, then shift.
1012	Not zero: Enter loop, then shift.
102	Not zero: Enter loop, then shift.
12	Not zero: Enter loop, then shift.
02	Zero: Exit loop.

unsigned negate( unsigned n ) {
   unsigned mask = 1;

   for ( unsigned i = n; i; i >>= 1 ) {
      n ^= mask;
      mask <<= 1;
   }

   return n;
}

It's unclear what result you expect for zero. The above produces zero.

Answer 5

What you want is a mask comprising all 1 bits up to and including the most significant set bit, and then XOR that with your original value:

uint32_t x = n; // n is your value
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return n ^ x;

Answer 6

A version for moden Intel/AMD processors that support the bit manipulation instruction extensions:

/* Compile with
 * gcc -O -mlzcnt -mbmi2 -Wall -Wextra foo.c
 * or
 * gcc -O -march=native -Wall -Wextra foo.c
 */

#include <stdio.h>
#include <inttypes.h>
#include <immintrin.h>

uint32_t flip_bits(uint32_t x) {
 return  _bzhi_u32(~x, 32 - _lzcnt_u32(x));
}

void print_binary(uint32_t x) {
  for (int i = 31; i >= 0; i--) {
    if (x & (1 << i)) {
      putchar('1');
    } else {
      putchar('0');
    }
  }
}

int main(int argc, char **argv) {
  for (int i = 1; i < argc; i++) {
    uint32_t x = strtoul(argv[i], NULL, 10);
    uint32_t y = flip_bits(x);
    printf("%" PRIu32 " (", x);
    print_binary(x);
    printf(") becomes %" PRIu32 " (", y);
    print_binary(y);
    fputs(")\n", stdout);
  }
}

It uses the LZCNT instruction to calculate the number of leading 0 bits, and BZHI to reset those bits to 0 after a bitwise-NOT of the original number. Might be interesting if you're looking to optimize a solution.