Link between modular arithmetic and bitwise AND in C expression

Question

I came across a C snippet that performs a nifty modular arithmetic operation using bitwise logic:

int a,b,c; 
c = (a + b - 1) & (- b) +b; 

The value of c is the smallest multiple of b greater than a+b (edited in response to John Bollinger's answer). I am trying to explain how this works to myself (I have a tenuous understanding of how modular arithmetic and the & operation could be related) but am falling short on insight. On the other hand it looks like I can express it as

c = (a+b) - ((a+b)%b) + (((a+b)%b)?b:0)

This expression is easy to understand. Moreover the appearance of the modular and ? operations suggests that the individual parts can be expressed as bitwise logic and somehow reduced to the expression at the top. But how? I leave it as an exercise if anyone wants to give it a go (this is NOT homework). Implementation need not be in C, and if there is an online ref that explains this you are welcome to provide it but will not be a complete answer. I'd like to see the transition from the bottom to the top expression in clear steps...

Comments This link suggests that this may apply when b is a power of 2. This other link explains that bitwise & does not distribute over addition.

Assume in the expression ...&(-b), (-b) can be replaced with (nums(int)-b), where nums(int) is the total number of possible ints in the representation.

Feel free to specify your favorite compiler/C version.

Sample code:

int a,b,c;
int alow, ahigh; 

b = 16;
alow = 8; 
ahigh = 20; 
printf("a+b      c    lcm(a+b,b) + ?b  \n");    
for (a=alow;a<ahigh;a++) {
    c = ((a+b-1) & (-b)) +b;
    printf("%5d   %5d    %5d   \n",a+b, c, (a+b) - ((a+b)%b) + (((a+b)%b)?b:0) );
}

Sample output:

  a+b      c    lcm(a+b,b) + ?b
   24      32       32
   25      32       32
   26      32       32
   27      32       32
   28      32       32
   29      32       32
   30      32       32
   31      32       32
   32      32       32
   33      48       48
   34      48       48
   35      48       48

Answer 1

On machines that use two's complement representation for negative numbers, if b is a power of 2 then in the representation of -b, the least-significant log2(b) bits have value zero, and all other bits have value one. Interpreted as an unsigned value, the least significant binary digit in that bit pattern has place value b. (Example: the int8_t with value -4 has bit pattern 11111100 in such a represenation.) This is the most common style of integer representation in use today, and where it matters, the rest of this answer will assume that mode of negative integer representation.

A value such as that can serve as a bitmask to mask off the binary digits having place value less than b from a non-negative integer. Given that we assumed a binary representation and b a power of 2, masking off the bits having lower place value necessarily results in a value divisible by b.

Now suppose a is non-negative and b is a power of 2. The value of a can be expressed as a non-negative multiple of b plus a remainder:

a == n * b + a % b

Now consider the expression (a + b - 1), and suppose that computing its value does not result in integer overflow. There are two cases:

Case 1: a % b == 0

In this case, a == n * b, so

(a + b - 1) == n * b + b - 1

. If we mask off the bits having place value less than b, we get

(a + b - 1) & (-b) == n * b == a

This is certainly the least multiple of b greater than or equal to a.

---

Case 2: a % b != 0

In this case,

(a + b - 1) == (n + 1) * b + a % b - 1

. If we mask off the bits having place value less than b, we get

(a + b - 1) & (-b) == (n + 1) * b

Since a is strictly between n * b and (n + 1) * b, this is again the least multiple of b greater than or equal to a.

---

Thus, your original assertion that

The value of [(a + b - 1) & (-b)] is the next largest number greater than a+b that is divisible by b

is an inaccurate characterization for the numeric representation I have supposed (including when b is not a power of 2, though I have not demonstrated that). Instead, under the assumptions described above, the expression computes the least multiple of b that is greater than or equal to a.

Your revised assertion follows directly from the above, however, by adding b to both sides of the expression. If (a + b - 1) & (-b) is the least multiple of b that is at least as large as a, then it follows that (a + b - 1) & (-b) + b is the least multiple of b that is at least as large as a + b.

Equivalent expressions that do not depend on numeric representation (but are still sensitive to overflow) would be

((a + b - 1) / b) * b + b

((a + b) / b) * b + b

((a / b) + 1) * b + ((a % b) ? b : 0)

The last of those maps rather directly onto the two cases presented above, and with a bit of care it can be rearranged to the second expression you present in your question.

Answer 2

I wouldn't trust any results you get from that. Per the C Standard, section 6.5:

Some operators (the unary operator ~,and the binary operators <<, >>, &, ^, and |, collectively described as bitwise operators) are required to have operands that have integer type. These operators yield values that depend on the internal representations of integers, and have implementation-defined and undefined aspects for signed types.