Diffrent usage of &- operator

Admin 1
Viewed 82

Look at the following code:

#include <stdio.h>

int main()
{
    int num, sum;
    scanf("%d", &num);
    sum = num - (num&-num);
    printf("%d", sum);
    return 0;
}

The line sum = num - (num& - num) returns value of the given number without the last 1 in binary format. For example if the num is equal to 6(110) it will give the value without the last 1. In this case 100 which is equal to 4. My question is how does &- work and how could do we do the same thing in octal numeral system?

octal binary c
2 Answers

What you have here is two separate operators: the bitwise AND operator & and the unary negation operator -. So the line in question is actually:

sum = num - (num & -num);

Assuming integers are stored in two's complement representation, negating a value means inverting all bits and adding one.

In the case that num is 6, (binary 00000110), -num is -6 which is 11111010. Then performing a bitwise AND between these two values results in 00000010 in binary which is 2 in decimal, so num - (num & -num) is 6 - 2 which is 4.

user_16871190

There is no &- operator. num - (num&-num) is num - (num & -num), where & performs the bitwise AND of num and its negation, -num.

Consider some number in binary, say 0011 0011 1100 11002 (spaces used for easy visualization). The negative of this is −0011 0011 1100 11002. However, we commonly represent negative numbers using two’s complement, in which a power of two is added. For 16-bit formats, we add 216, which is 1 0000 0000 0000 00002. So, to represent −0011 0011 1100 11002, we use 1 0000 0000 0000 00002 + −0011 0011 1100 11002 = 1100 1100 0011 01002.

Observe what happens in this subtraction, column by column from the right:

  • In the rightmost column, we have 0−0, which yields 0.
  • The next column also has 0−0, yielding 0.
  • The next column has 0−1. This yields 1 with a borrow from the column to the left.
  • The next column has 0−1−1 (where the second −1 is the borrow). This yields 0 with another borrow.
  • Because the minuend (the number being subtracted from) has all zeros up to that initial 1, this borrow is never satisfied, so it propagates throughout the bits.

Thus the result is:

  • Starting at the right, 0s remain 0s.
  • The first 1 stays a 1 but starts a borrow chain.
  • Because of the borrow, all bits to the left of that flip from 0 to 1 or 1 to 0.

Thus the subtrahend (the number being subtracted) and the result differ in all bits to the left of the first 1. And they both have 0s to the right of the first 1. So the only bit they both have set is that first 1.

Therefore, when two’s complement is in use, the result of num & -num is the lowest 1 bit that is set in num.

Then num - (num & -num) subtracts this bit from num, leaving it as num with its lowest 1 bit changed to 0.

user_2982250
Related