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

Question

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

So are are you trying to turn the number 1234 into the number 12? Or trying to get the number 34 out of the number 1234? Or trying to turn 1234 into 1200? (I think you are trying to turn it into 12, but want to make sure). — SirPentor, May 30 '12 at 19:14
Out of curiosity, is there any reason you're trying to do this? Is this just for fun? — templatetypedef, May 30 '12 at 19:16
Yeah, fun. and for bug tracing. (I'm dealing with some bug, and I suspect the person who wrote the code use bitwise ops. So I'd like to know if this is what they did) — One Two Three, May 30 '12 at 19:17
only bitwise operations ? no addition ?, no if ? no loop of any kind ? — Jerome WAGNER, May 30 '12 at 19:18
@npe: No this is not homework. (It's summer! Gah! I'm trying not to think of the school~! :P ) — One Two Three, May 30 '12 at 19:18
Ok, here's the thing. Given this number `200901`, the function would return `2009` because it's supposed to truncate the last two digits, but if I give it `-200901`, it'd return `186113241`. So I'm trying to find out, if the bug is due to the fact that its owner wasn't aware of the sign when doing the shifting or whatever it is that he did to truncate the number. — One Two Three, May 30 '12 at 19:25
Bitwise operations work on powers of two. Working on powers of ten is going to be difficult, awkward, or possibly downright impossible. — Louis Wasserman, May 30 '12 at 19:29
Well, ok. Then does anyone happen to have any idea what might've been done to produce the weird result that I posted in my comment above? — One Two Three, May 30 '12 at 19:32
Why do you think the code in question is using bitwise operations? Maybe it is doing character operations and that is the cause of the problem. — dwikle, May 30 '12 at 19:34
Uhm, the function takes an input of integer, so if the code isn't using bitwise or regular maths operations, what else could it be using? (Character operations seem slow. And I'm pretty sure that performance is guaranteed for this function) — One Two Three, May 30 '12 at 19:38
@OneTwoThree can your test this function on more numbers? And give it's output. — Mikita Belahlazau, May 30 '12 at 19:40
Can't you simply show us the code of that function that's causing you trouble? — Daan, May 30 '12 at 19:44
@Daan If I had access to the code, I wouldn't be asking for an answer~! — One Two Three, May 30 '12 at 19:45
@OneTwoThree if it's java you always can decompile it and see source code — Mikita Belahlazau, May 30 '12 at 19:46
In that case you'll have to do as @Nikita suggested and give us some more examples of how this mysterious function works... — Daan, May 30 '12 at 19:51
Ok! I have updated my question with some explanation as to why I'm doing this kind of stuff. :) and some input/outputs — One Two Three, May 30 '12 at 20:00
Anyone have the slightest idea/suspect what might be the problem? :) — One Two Three, May 30 '12 at 20:30
This looks like it has a pattern. And the number `186xxxxxx` looks suspiciously familiar. I'm trying to remember where I've seen it before. — One Two Three, May 30 '12 at 20:35
@OneTwoThree What is the result of the function for 0, 1 and 100? — dwikle, May 31 '12 at 01:29
These comments are getting long. Consider using the [chat] link to move the conversation to chat. When you start a chat, it automatically imports the comments to the chat so you don't lose any of the context. — jamesmortensen, May 31 '12 at 04:24

score 1 · Answer 1 · edited May 23 '17 at 11:56

1

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

edited May 23 '17 at 11:56

Community

1
1

answered May 30 '12 at 20:18

Jerome WAGNER

21,986
8
62
77

I don't know. Really. I don't have access to the code. But if this'd produce the same output for the negative cases I listed, then I guess you're right~ :) – One Two Three May 30 '12 at 20:26
Well, sorry, just to clarify. So this in Java code would be: `n = n >> 7 ^ n >> 9 ^ n >> 13 ^ n >> 14 ^ n >> 15 ^ n >> 16 ^n >> 18 ^ n >> 20 ^ n >> 21 ^ n >> 22 ^ n >> 27 ^ n >> 29;` ? I tried that and always got 1976 as the output no matter what the value of n was initialized to – One Two Three May 30 '12 at 20:28
modified my answer with a java example. Still looking into xor and your negative corner cases – Jerome WAGNER May 30 '12 at 21:00
Your code always give a number that is 1 unit less than the correct result. So for instance `200901 ===>[your function] ===> 2008`, but it's supposed to be `2009` – One Two Three May 30 '12 at 21:27
yes. not always. you can try with 12345 for example. These are rounding issues. for example, for 200901 => 257150 / 128 => 2008.98 ; A scrutiny for rounding issues would be necessary on my solution. In any case I can't reproduce the results you have with negative values. Sorry. – Jerome WAGNER May 30 '12 at 21:33

score 0 · Answer 2 · answered May 30 '12 at 19:55

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.

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

2 Answers2