CODEWITHSUNDEEP
c++debuggingmathbit-manipulation
One Two Three
One Two Three

Reputation: 23497

bitwise operation(s) to truncate the last two digits of a number

I have an integer n, and I'd like to truncate the last two digits of the number using only bitwise operations.

So, in regular arithmetic, it'd be as simple as n /= 100. But how would this be done with bitwise operation(s)?

Thanks,

(This is in c++, by the way)

[Edit]: For instance, given the number 1234, I'd like to get 12. (truncate the last two digits 34)

[Edit2:] Let me rephrase the question. I'm trying to understand why a particular function that's supposed to truncate the last two digits of a number kind of screws things up when given a negative input. (And I don't have the code for this function)

Here's the set of inputs and their corresponding outputs

-200901 ==> 186113241

-200801 ==> 186113242

-200701 ==> 186113243

-200601 ==> 186113244

-190001 ==> 186113350

-190101 ==> 186113349

-190201 ==> 186113348

-190301 ==> 186113347

Upvotes: 4

Views: 2320

Answers (2)

Jerome WAGNER
Jerome WAGNER

Reputation: 22412

Here you want to divide by a constant : 100

Following How can I multiply and divide using only bit shifting and adding? that was given by Suraj Chandran in his comments,

You can re-interpret this as a multiplication by 1/100.

In base 2, 1/100 can be approximated to 1/2^7 * ( 1/2^0 + 1/2^2 + 1/2^6+ 1/2^7+ 1/2^8+ 1/2^9 + 1/2^11+ 1/2^13+ 1/2^14+ 1/2^15+ 1/2^20+ 1/2^22 + 1/2^26 + 1/2^27 + 1/2^28 1/2^29)

so you have and approximation with (n >> 0 + n >> 2 + n >> 6 + n >> 7 + n >> 8 + n >> 9 + n >> 11 + n >> 13 + n >> 14 + n >> 15 + n >> 20 + n >> 22 + n >> 26 + n >> 27 + n >> 28 + n >> 29) >> 7

Is this more or less what you have in your legacy code ?

I wouldn't dare saying that this will always give you the correct answer as I have done no scrutiny on the effects of the approximations here and there may very well be rounding issues in some cases.

In java code that would be

remaining = (( n>>0 ) + (n >> 2) + (n >> 6) + (n >> 7) + (n >> 8) + (n >> 9) + (n >> 11) + (n >> 13) + (n >> 14) + (n >> 15) + (n >> 20) + (n >> 22) + (n >> 26) + (n >> 27) + (n >> 28) + (n >> 29)) >> 7;

added an example on http://ideone.com/8UlD7

I coulnd't find a way to replace the additions by bitwise operations + could not reproduce the results you have with your negative values

Upvotes: 1

Wormbo
Wormbo

Reputation: 4992

Ok, another approach.

1234 : 100 = 12, remainder 34

Now in binary, I hope I didn't mess it up:

 100 1101 0010 : 110 0100 = 1100 Result
- 11 0010 0
-----------
   1 1011 00
  -1 1001 00
  ----------
     0010 001
    -       0
    ---------
      010 0010
     -       0
     ---------
       10 0010 remaining

Have fun converting that to an algorithm. It will be slow as hell compared to x /= 100, no matter how you do it.

Upvotes: 0

Related Questions