CODEWITHSUNDEEP
cdivision
Dan
Dan

Reputation: 67

Division by power of 2 with round toward zero

I need to compute a number (a/(2**b) using only bitwise operators such as ! & ^ ~ and shifts. I was given the following hint but I'm new to C and I dont know what the code means: 

int bias = x>0 ? 0 : ((1<<n)-1);

Can anyone explain it to me?

I thought a>>b would work but I dont think it works for negative numbers.

Upvotes: 0

Views: 6808

Answers (4)

J. Gareth Moreton
J. Gareth Moreton

Reputation: 1

As answered already, the ? : operators are the 'ternary operator'. To the left of the ? is a condition. If the condition is true, the block returns what's between the ? and :, and if false, returns what's to the right of :.

In the context of signed division by 2 rounding towards zero. If the numerator is positive, then a logical right-shift gives the correct result. For negative (two's complement) integers it takes a bit more work. The first step is to replace the logical shift with an aritmetic one. For exact multiples of 2, the correct answer is still given, but other values are rounded towards minus infinity. Here, adding the "bias" corrects this.

Therefore, for positive integers, no bias is required, but for negative integers, a bias of 2b - 1 has to be added to the numerator. The full code is hence something like the following:

int div2(int x, int b)
{
  int bias = x>0 ? 0 : ((1<<b)-1);
  return (x+bias)>>b; // Note this only works if >> is an arithmetic shift.
}

Note that some care has to be taken if b is equal to or greater than 32, as (1<<b) may not produce what you expect (same goes with the below example).

In x86 assembly language, you might want something like the following (I hope my assembly knowledge is still good!):

  ; Assume the numerator is in ECX and the value of b is in EDX for this example

  ; Prologue to preserve some extra registers
  PUSH  EBX
  PUSH  ESI

  ; Register rearrangement (only CL is valid for variable shifts)
  MOV   EAX, ECX
  MOV   CL,  DL

  ; Prepare bias mask
  MOV   ESI, 1
  SHL   ESI, CL
  SUB   ESI, 1

  ; Apply bias if numerator is negative
  XOR   EBX, EBX
  TEST  EAX, EAX
  CMOVS EBX, ESI ; Sets EBX to ESI if the sign bit is set by TEST, otherwise EBX is left as is (equal to 0)

  ; Perform arithmetic shift with bias
  ADD   EAX, EBX
  SAR   EAX, CL

  ; Epilogue
  POP   ESI
  POP   EBX

  ; Result in EAX
  RET

This is a homework-like question, but it is also useful in the field of compiler development.

Please note that this isn't the fastest algorithm around. In assembly, it would be something like this:

  ; Assume the numerator is in ECX and the value of b is in EDX for this example
  PUSH EBX

  MOV  EAX, ECX
  MOV  EBX, ECX
  MOV  ECX, EDX

  MOV  EDX, 1
  SHL  EDX, CL
  SUB  EDX, 1

  SAR  EAX, 31
  AND  EAX, EDX

  ADD  EAX, EBX
  SAR  EAX, CL

  POP  EBX
  RET

Upvotes: 0

Mike Spear
Mike Spear

Reputation: 882

Sigh... this is a homework question. The student is asking for help with an assignment from the Computer Systems, a Programmers' Perspective textbook.

For future reference, any time someone says "I'm only allowed to use the XYZ operators to do something", it's probably a homework question.

I don't suppose there's a way to take reputation away from people who ask for help with homework questions, is there?

Upvotes: -1

thing
thing

Reputation: 1

well,x<<n works correctly for positive numbers. so why dont you just use something like result=if sign=1 then (x<<n) else(-x<<n) (replace the iftehenelse by some masking with the sign bit)

Upvotes: 0

jkerian
jkerian

Reputation: 17016

That particular bit of code gives you a bias of 0 if x is positive. Otherwise it produces a mask of the lower n bits. The x = a ? b : c; pattern is called the ternary operator(technically the 'conditional operator', apparently) in C.

n      (1<<n)    (1<<n)-1     binary
0        0x01       0x00     00000000
1        0x02       0x01     00000001
2        0x04       0x03     00000011
3        0x08       0x07     00000111
4        0x10       0x0F     00001111
5        0x20       0x1F     00011111
6        0x40       0x3F     00111111
7        0x80       0x7F     01111111
           ...

Upvotes: 3

Related Questions