Diffrent usage of &- operator

Question

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?

@Jabberwocky - Probably just a cousin of the [`-->` operator](https://stackoverflow.com/questions/1642028/what-is-the-operator-in-c). — StoryTeller - Unslander Monica, Aug 08 '20 at 19:33
@Jabberwocky I saw it on National Informatic Olympiad of Turkey. — , Aug 08 '20 at 19:36

score 3 · Accepted Answer · answered Aug 08 '20 at 19:35

3

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.

answered Aug 08 '20 at 19:35

dbush

205,898
23
218
273

In general, the pattern `x&-x` is "lowest set bit of the value `x`, by itself", and is something of a standard idiom. – R.. GitHub STOP HELPING ICE Aug 08 '20 at 20:07
And while the example here is subtracting that to remove the lowest bit, you can also just use `x&(x-1)` to get a value that's the input with the lowest set bit removed. – R.. GitHub STOP HELPING ICE Aug 08 '20 at 20:09

score 3 · Answer 2 · answered Aug 08 '20 at 19:39

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 1100₂ (spaces used for easy visualization). The negative of this is −0011 0011 1100 1100₂. However, we commonly represent negative numbers using two’s complement, in which a power of two is added. For 16-bit formats, we add 2¹⁶, which is 1 0000 0000 0000 0000₂. So, to represent −0011 0011 1100 1100₂, we use 1 0000 0000 0000 0000₂ + −0011 0011 1100 1100₂ = 1100 1100 0011 0100₂.

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.

Diffrent usage of &- operator

2 Answers2