bitwise division rounding to nearest zero

Question

I want to perform an signed integer bitwise division by a power of 2. However, I encounter several problem. I just wonder if anyone can help me.

First, I try to use bit shifting alone:

int result = number >> n;

However, I got a problem when I try to divide a negative number. (it always round with a number with bigger magnitude. example: -9/4=-3 instead of -2. So, I look this problem in the internet, that end me up with this solution:

int result = (number + (1<<n)-1) >> n;

However, when I try 11/4 = 3 instead of 2

Any suggestions? I can only use ! ~ & ^ | + << >> (no loop or if/switch allowed)

its not clear for me. 1) are you using `/` to obtain the result **or** 2)using `>>` to perform the equivalent division? — Koushik Shetty, Apr 10 '13 at 04:47
@Koushik, He says he can use only these operators: ! ~ & ^ | + << >>. Also, no loops or if conditions/switches. — Anish Ramaswamy, Apr 10 '13 at 04:51
@AnishRam i just wanted to make sure he dint leave out `/`. now its clear to me. — Koushik Shetty, Apr 10 '13 at 05:00
A helpful link for you http://stackoverflow.com/questions/11694546/divide-a-number-by-3-without-using-operators — Grijesh Chauhan, Apr 10 '13 at 05:05

Alexey Frunze · Accepted Answer · 2013-04-10T06:14:33.170

The following method is bad because it relies on:

right shifts of negative integers being arithmetic shifts (may not be the case)
signed integers being in the 2's complement representation (extremely rarely may not be the case)
integers not having any padding bits (these days on modern CPUs you won't find padding bits, although the standard allows their existence)

And it may cause undefined behavior on some dividends (e.g. INT_MIN) due to signed integer overflow.

Therefore it isn't portable and isn't guaranteed to work always. You have been warned.

#include <stdio.h>
#include <limits.h>

int DivByShifting1(int n, unsigned shift)
{
  int sgn = n >> ((sizeof(int) * CHAR_BIT) - 1);
  return ((((n + sgn) ^ sgn) >> shift) + sgn) ^ sgn;
}

int main(void)
{
  int n, s;
  for (n = -10; n <= 10; n++)
    for (s = 0; s <= 4; s++)
      printf("%d / %d = %d\n", n, 1 << s, DivByShifting1(n, s));
  return 0;
}

Output (ideone):

-10 / 1 = -10
-10 / 2 = -5
-10 / 4 = -2
-10 / 8 = -1
-10 / 16 = 0
-9 / 1 = -9
-9 / 2 = -4
-9 / 4 = -2
-9 / 8 = -1
-9 / 16 = 0
-8 / 1 = -8
-8 / 2 = -4
-8 / 4 = -2
-8 / 8 = -1
-8 / 16 = 0
-7 / 1 = -7
-7 / 2 = -3
-7 / 4 = -1
-7 / 8 = 0
-7 / 16 = 0
-6 / 1 = -6
-6 / 2 = -3
-6 / 4 = -1
-6 / 8 = 0
-6 / 16 = 0
-5 / 1 = -5
-5 / 2 = -2
-5 / 4 = -1
-5 / 8 = 0
-5 / 16 = 0
-4 / 1 = -4
-4 / 2 = -2
-4 / 4 = -1
-4 / 8 = 0
-4 / 16 = 0
-3 / 1 = -3
-3 / 2 = -1
-3 / 4 = 0
-3 / 8 = 0
-3 / 16 = 0
-2 / 1 = -2
-2 / 2 = -1
-2 / 4 = 0
-2 / 8 = 0
-2 / 16 = 0
-1 / 1 = -1
-1 / 2 = 0
-1 / 4 = 0
-1 / 8 = 0
-1 / 16 = 0
0 / 1 = 0
0 / 2 = 0
0 / 4 = 0
0 / 8 = 0
0 / 16 = 0
1 / 1 = 1
1 / 2 = 0
1 / 4 = 0
1 / 8 = 0
1 / 16 = 0
2 / 1 = 2
2 / 2 = 1
2 / 4 = 0
2 / 8 = 0
2 / 16 = 0
3 / 1 = 3
3 / 2 = 1
3 / 4 = 0
3 / 8 = 0
3 / 16 = 0
4 / 1 = 4
4 / 2 = 2
4 / 4 = 1
4 / 8 = 0
4 / 16 = 0
5 / 1 = 5
5 / 2 = 2
5 / 4 = 1
5 / 8 = 0
5 / 16 = 0
6 / 1 = 6
6 / 2 = 3
6 / 4 = 1
6 / 8 = 0
6 / 16 = 0
7 / 1 = 7
7 / 2 = 3
7 / 4 = 1
7 / 8 = 0
7 / 16 = 0
8 / 1 = 8
8 / 2 = 4
8 / 4 = 2
8 / 8 = 1
8 / 16 = 0
9 / 1 = 9
9 / 2 = 4
9 / 4 = 2
9 / 8 = 1
9 / 16 = 0
10 / 1 = 10
10 / 2 = 5
10 / 4 = 2
10 / 8 = 1
10 / 16 = 0

Note that ((sizeof(int) * CHAR_BIT) - 1) is a compile-time constant and therefore * and - can be allowed.

Another version, which is very similar, but does not require right shifts of negative integers to be arithmetic shifts and is free of signed integer overflow (2's complement-ness and padding bits are still limitations, but virtually in-existent in today's practice):

#include <stdio.h>
#include <limits.h>
#include <string.h>

int DivByShifting2(int n, unsigned shift)
{
  unsigned un = n;
  unsigned sgn = 1 + ~(un >> ((sizeof(int) * CHAR_BIT) - 1));
  un = ((((un + sgn) ^ sgn) >> shift) + sgn) ^ sgn;
  memcpy(&n, &un, sizeof n);
  return n;
}

int main(void)
{
  int n, s;
  for (n = -10; n <= 10; n++)
    for (s = 0; s <= 4; s++)
      printf("%d / %d = %d\n", n, 1 << s, DivByShifting2(n, s));
  return 0;
}

Output (ideone):

-10 / 1 = -10
-10 / 2 = -5
-10 / 4 = -2
-10 / 8 = -1
-10 / 16 = 0
-9 / 1 = -9
-9 / 2 = -4
-9 / 4 = -2
-9 / 8 = -1
-9 / 16 = 0
-8 / 1 = -8
-8 / 2 = -4
-8 / 4 = -2
-8 / 8 = -1
-8 / 16 = 0
-7 / 1 = -7
-7 / 2 = -3
-7 / 4 = -1
-7 / 8 = 0
-7 / 16 = 0
-6 / 1 = -6
-6 / 2 = -3
-6 / 4 = -1
-6 / 8 = 0
-6 / 16 = 0
-5 / 1 = -5
-5 / 2 = -2
-5 / 4 = -1
-5 / 8 = 0
-5 / 16 = 0
-4 / 1 = -4
-4 / 2 = -2
-4 / 4 = -1
-4 / 8 = 0
-4 / 16 = 0
-3 / 1 = -3
-3 / 2 = -1
-3 / 4 = 0
-3 / 8 = 0
-3 / 16 = 0
-2 / 1 = -2
-2 / 2 = -1
-2 / 4 = 0
-2 / 8 = 0
-2 / 16 = 0
-1 / 1 = -1
-1 / 2 = 0
-1 / 4 = 0
-1 / 8 = 0
-1 / 16 = 0
0 / 1 = 0
0 / 2 = 0
0 / 4 = 0
0 / 8 = 0
0 / 16 = 0
1 / 1 = 1
1 / 2 = 0
1 / 4 = 0
1 / 8 = 0
1 / 16 = 0
2 / 1 = 2
2 / 2 = 1
2 / 4 = 0
2 / 8 = 0
2 / 16 = 0
3 / 1 = 3
3 / 2 = 1
3 / 4 = 0
3 / 8 = 0
3 / 16 = 0
4 / 1 = 4
4 / 2 = 2
4 / 4 = 1
4 / 8 = 0
4 / 16 = 0
5 / 1 = 5
5 / 2 = 2
5 / 4 = 1
5 / 8 = 0
5 / 16 = 0
6 / 1 = 6
6 / 2 = 3
6 / 4 = 1
6 / 8 = 0
6 / 16 = 0
7 / 1 = 7
7 / 2 = 3
7 / 4 = 1
7 / 8 = 0
7 / 16 = 0
8 / 1 = 8
8 / 2 = 4
8 / 4 = 2
8 / 8 = 1
8 / 16 = 0
9 / 1 = 9
9 / 2 = 4
9 / 4 = 2
9 / 8 = 1
9 / 16 = 0
10 / 1 = 10
10 / 2 = 5
10 / 4 = 2
10 / 8 = 1
10 / 16 = 0

@R.. rightfully reminds that the conversion from a signed int to an unsigned int can be done by adding 0u (unsigned 0).

And he also reminds that un can be returned directly instead of doing memcpy() to n. The conversion should be implementation-defined, but in 2's complement implementations of C, bit-for-bit copy is practically always the case.

Could you explain what `n >> ((sizeof(int) * CHAR_BIT) - 1)` in your `DivByShifting1` function does? — Anish Ramaswamy, Apr 10 '13 at 05:38
@AnishRam [Arithmetic shift](http://en.wikipedia.org/wiki/Arithmetic_shift). It gives you 0 for n >= 0 and -1 for n < 0. — Alexey Frunze, Apr 10 '13 at 05:42
Personally, I would use the implementation-defined conversion from `unsigned` to `int` (taking place in the `return` statement) rather than `memcpy`... — R.. GitHub STOP HELPING ICE, Apr 10 '13 at 06:10

score 1 · Answer 2 · answered Apr 10 '13 at 05:38

1

Just use the / operator:

int result = number / (1 << n);

Any decent compiler will compile this to the optimal bitshift with fixup for "rounding" of negative results.

answered Apr 10 '13 at 05:38

R.. GitHub STOP HELPING ICE

208,859
35
376
711

The point of the exercise is to avoid explicit division in the source code. – Alexey Frunze Apr 10 '13 at 05:41
Then I don't think it can be done portably, since `>>` is implementation-defined for negative operands. You'd at least need a way to condition the expression on whether the operand is negative... – R.. GitHub STOP HELPING ICE Apr 10 '13 at 05:43
Or it will use `idiv`; whichever is more efficient – Aki Suihkonen Apr 10 '13 at 05:46
You could cast the signed integer to unsigned and use the most significant bit as the sign bit value. I think, it'll still be doable, although significantly longer. – Alexey Frunze Apr 10 '13 at 05:48
Yeah, just did added a version not relying on the implementation-defined behavior of `>>`. – Alexey Frunze Apr 10 '13 at 06:04
I didn't see casts in the list of allowed operators. You could use `+0U` to convert to unsigned, but then there's no way to convert back without a cast or assignment... – R.. GitHub STOP HELPING ICE Apr 10 '13 at 06:06
Yep, I've thought of adding unsigned 0, but it's equivalent, so, not a real problem. – Alexey Frunze Apr 10 '13 at 06:07

score 0 · Answer 3 · answered Apr 10 '13 at 04:57

maybe this should help you.

1) if your using / operator then the standard says (ISO/IEC TR3 in 6.5.5 Multiplicative operators)that the result of the / operator is the quotient from the division of the first operand by the second.

2) if your using >> the standard says (ISO/IEC TR3 in 6.5.7) that the result of >> where the LHS operand is a signed type and negative then the resulting value is implementation defined.

so / will give you the result as you desired.

but >> on signed && negative number is dependant on your compiler.

score 0 · Answer 4 · answered Apr 10 '13 at 05:48

Judging from the disassembly of int div(int a){return a/4;}:

leal 3(%rdi), %eax
testl %edi, %edi
cmovns %edi, %eax
sarl $2, %eax

one has to adjust the operand by (1<<n)-1 if and only if the operand is negative.

An unconditional method would be to use sgn(a)*(abs(a)>>n); both of which can be implemented with branchless bitmagic relying on the implementation defined behaviour.

bitwise division rounding to nearest zero

4 Answers4

Linked