Solved

Binary OR operator confusion!

Posted on 2011-02-14
19
369 Views
Last Modified: 2012-05-11
Ah hello.

This is a very short question.  I have the following code:

int n = /* some value */
int x = n | 0x1F; // 31

Open in new window


The result is that x will be set to the nearest multiple of 32, less one.  This works, but I cannot logically see *how*.  I understand what is going on, with the OR'ing of each individual bit, the result bit only being set if either of the operands corresponding bit is set etc, but why does it result in x being "nearest multiple less one" and how can we change it so we get the nearest multiple of any value, not less one?

If I say

int n = /* some value */
int x = n | 0x20; // 32

Open in new window


x does not get rounded the nearest multiple of 32!

Can someone please explain this?

TIA
0
Comment
Question by:mrwad99
  • 4
  • 4
  • 3
  • +5
19 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 34888491
In the first example the OR affects all the 5 lower bits, ensuring they will always be set but in the second example only the 6th bit is guaranteed to be set, the other lower 5 will only be set if n has them set already.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 34888505
Visualised...

010101
011111
------
011111

010101
100000
------
110101

Open in new window

0
 
LVL 30

Expert Comment

by:Zoppo
ID: 34888518
> nearest multiple of 32

I guess this statement isn't correct in any case. I.e. look at this:

int n = 0x20;
int x = 0x20 | 0x1f;

Here now 'x == 0x3f' which is 63 which for sure isn't the nearest multiple of 32 less one when starting with 0x20 (=32) - the nearest here would be exected to be '0x1f' again ...

ZOPPO
0
 
LVL 45

Expert Comment

by:Kdo
ID: 34888523
Hi mrwad,

If you look at the binary representation of 32, it might help.

  000100000

If a bit is set to the left of the 1 bit, the value is 32 * N so those bits don't matter.


31 looks like this:

  000011111

All bits to the right of 2^5 are set.


So to get the value you want, the algebra is 32 * N + 31.  That happens simply by setting the lower 5 bits in the word no matter what the higher bits are.

  X | 0x01F;

That simply sets the 5  lowest order bits of the word, ensuring that the value is 1 less than a multiple of 32.


Good Luck,
Kent
0
 
LVL 32

Expert Comment

by:phoffric
ID: 34888574

Consider a byte of the form:
bbb00000 (where b = 0 or 1)

Do you see that bbb00000 = bbb * 2^5 ?

For example, 10100000 = 5 * 2^5 = 5 * 32 = 160

Now consider a byte of the form
bbb11111 = bbb * 2^5 + 0x1F

Since 0x1F = 0x20 - 1, substitute:

bbb11111 = bbb * 2^5 + 0x20 - 1 = bbb * 2^5 + 2^5 - 1 = (bbb + 1)*2^5 - 1
0
 
LVL 32

Expert Comment

by:phoffric
ID: 34888785
>> nearest multiple of any value
"nearest" may be ambigous. For example:

If n = 31, then nearest multiple is 32.
If n = 32, then nearest multiple is 32.
If n = 33, then nearest multiple is 32.
If n = 61, then nearest multiple is 64.

On the other hand, if you mean nearest to mean the next highest multiple as in:

If n = 31, then nearest next highest multiple is 32.
If n = 32, then nearest next highest multiple is 64.
If n = 33, then nearest next highest multiple is 64.
If n = 61, then nearest next highest multiple is 64.

then you could just add 1 to your original expression:
int x = (n | 0x1F) + 1;

Open in new window

But, if you meant:
If n = 31, then nearest multiple is 32.
If n = 32, then nearest multiple is 32.
If n = 33, then nearest multiple is 64.
If n = 61, then nearest multiple is 64.

then you could first check to see whether n is already a multiple of 32 and if it is use that value.
int y = (  (( n & ~0x1F ) == n) ? n : (n | 0x1F) + 1);

Open in new window

0
 
LVL 32

Expert Comment

by:sarabande
ID: 34888795
instead of 'nearest' it should be 'next'.

the nearest or next multiple of any number cannot made by bitwise or. muliplication is derived from addition (like you learned it in school). only for numbers that are power of 2 you can replace it by bit operations.

to not have -1 simply add 1 to the result.

   x = (x | 0x1f) + 1;

Sara
0
 
LVL 19

Author Comment

by:mrwad99
ID: 34888931
Oh dear.

I have read and re-read these comments and the only thing I understand is ZOPPO saying that it does not work as expected when we start with 32.  So I guess the caveat to that is "the nearest multiple of 32, less 1, *after the input value*.

RX, thanks: I can see what you are saying about bits being set perfectly clearly (in fact before I even asked this question I did the same thing) but still lack the knowledge of *why* this works...

Kent, you said

>> If a bit is set to the left of the 1 bit, the value is 32 * N so those bits don't matter.

What is 'N' ???

phoffric, what you have shown looks nice, but I am afraid it is light years ahead of where I currently am.  Sorry.
0
 
LVL 32

Assisted Solution

by:phoffric
phoffric earned 25 total points
ID: 34888981
Sorry about that :(
Well, at least I can give you a program and its output, so maybe you can choose which version you prefer:
int main(void)  
{  
   int n;
   for( n = 30; n<67; ++n ) {
      int x = (n | 0x1F) + 1;
      int y = (  (( n & ~0x1F ) == n) ? n : (n | 0x1F) + 1);
      printf("%2d: x = %2d   y = %2d\n", n, x, y);
   } 
}  

Open in new window

OUTPUT:
30: x = 32   y = 32
31: x = 32   y = 32
32: x = 64   y = 32
33: x = 64   y = 64
34: x = 64   y = 64
35: x = 64   y = 64
36: x = 64   y = 64
37: x = 64   y = 64
38: x = 64   y = 64
39: x = 64   y = 64
40: x = 64   y = 64
41: x = 64   y = 64
42: x = 64   y = 64
43: x = 64   y = 64
44: x = 64   y = 64
45: x = 64   y = 64
46: x = 64   y = 64
47: x = 64   y = 64
48: x = 64   y = 64
49: x = 64   y = 64
50: x = 64   y = 64
51: x = 64   y = 64
52: x = 64   y = 64
53: x = 64   y = 64
54: x = 64   y = 64
55: x = 64   y = 64
56: x = 64   y = 64
57: x = 64   y = 64
58: x = 64   y = 64
59: x = 64   y = 64
60: x = 64   y = 64
61: x = 64   y = 64
62: x = 64   y = 64
63: x = 64   y = 64
64: x = 96   y = 64
65: x = 96   y = 96
66: x = 96   y = 96

Open in new window

0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 25 total points
ID: 34889009
The "click" of understanding will probably be made by realizing that all multiples of 32 minus 1 have something in common :

        31        ->   00011111
        63        ->   00111111
        95        ->   01011111
        127     ->   01111111
        159     ->   10011111
        etc.

As you see, all of them have their lowest 5 bits set to 1.

And every value that has it's lowest 5 bits set to 1 has to be a multiple of 32 minus 1.


Note that this would also work for other multiples of powers-of-two minus 1, like multiples of 16 minus 1 (which would have their lowest 4 bits set to 1), etc.
0
 
LVL 45

Expert Comment

by:Kdo
ID: 34889025
Hi Mrwad,

N is any integer.


  0000 0001 1111    N = 0, Result = 0 * 32 + 31
  0000 0011 1111    N = 1, Result = 1 * 32 + 31
  0000 0101 1111    N = 2, Result = 2 * 32 + 31
  0000 0111 1111    N = 3, Result = 3 * 32 + 31
etc...


Kent
0
 
LVL 32

Expert Comment

by:sarabande
ID: 34889043
the 'or' always adds to number x. so what zoppo said it is never rounding down to nearest multiple of 32 but is always rounding up to next higher multiple of 32 (minus 1).

Sara
0
 
LVL 19

Author Comment

by:mrwad99
ID: 34889766
OK, Kent I see what you mean now.

0000 0001 1111    N = 0, Result = 0 * 32 + 31
0000 0011 1111    N = 1, Result = 1 * 32 + 31
0000 0101 1111    N = 2, Result = 2 * 32 + 31
0000 0111 1111    N = 3, Result = 3 * 32 + 31

Here, you are getting the value of 'N' by converting to decimal the values of the bits after and including the bit with value 32, starting again at 0, i.e. those shown in bold.  This is an interesting technique and one that I was not aware of.

"If a bit is set to the left of the 1 bit, the value is 32 * N so those bits don't matter."

I don't know what you mean there, can you clarify?

Infinity:

"The "click" of understanding will probably be made by realizing that all multiples of 32 minus 1 have something in common :"

Sure, but how can we be sure that this is the case?  (Sorry again) Can anyone give me some logical proof please?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 34889794
>> Sure, but how can we be sure that this is the case?  (Sorry again) Can anyone give me some logical proof please?

That's something that Kdo's previous post explains quite well.
0
 
LVL 19

Author Comment

by:mrwad99
ID: 34889826
Right, so the missing piece then is what "If a bit is set to the left of the 1 bit, the value is 32 * N so those bits don't matter." means...
0
 
LVL 45

Accepted Solution

by:
Kdo earned 75 total points
ID: 34889891
>>"If a bit is set to the left of the 1 bit, the value is 32 * N so those bits don't matter."

>>I don't know what you mean there, can you clarify?


Sure.  :)

As the examples evolved, that statement needed refinement.  So here goes.

When the lower 5 bits are zero, ANY combination of the other bits results in a value that is a multiple of 32.  So to fulfill the need for a value that is 1 less than a multiple of 32, you can add 31 to, or subtract 1 from, a multiple of 32.

Setting all 5 lower bits to 1 adds 31.  In C code you might write it as:

   Result = mod (value, 32) + 31;

That is identical in functionality to your original example:

   Result = X | 0x1F;


Your method is slightly faster, though probably not noticeable.  I would expect that the timing difference in executing 1,000,000 of each is considerably less than a second.


Kent

Kent
0
 
LVL 8

Expert Comment

by:lomo74
ID: 34894810
> how can we change it so we get the nearest multiple of any value, not less one?

int x = 55; /* some value */
int y = 6; /* round to the next multiple of this value */
int z = x - (x % y) + (x % y ? y : 0);  /* rounded value = 60 */

if the number you want to round to is a power of two (i.e. you want to round to 2, 4, 8, 16 and so on) then this is also valid (and faster):

int x = 55; /* some value */
int y = 16; /* round to the next multiple of this power of two */
int z = (x + y - 1) & -y; /* rounded value = 64 */
0
 
LVL 19

Author Closing Comment

by:mrwad99
ID: 34895522
Kent:

"When the lower 5 bits are zero, ANY combination of the other bits results in a value that is a multiple of 32.  So to fulfill the need for a value that is 1 less than a multiple of 32, you can add 31 to, or subtract 1 from, a multiple of 32."

That is what made the penny drop.  Thank you very much :-)

Everyone else:

Thank you all *very* much for participating in this, and helping me understand.  I *really* appreciate it.  Please don't be offended if you did not get points: it is not that I did not value your input but simply that I wanted to award points to the answers that I feel would help someone else understand this issue also.
0
 
LVL 45

Expert Comment

by:Kdo
ID: 34896137
Hi Mrwad,

Sometimes, we have to dance to get where we're going.  Sorry.

It occurred to me on the drive in this morning that there was a much easier way to explain this.  (A little Steppenwolf is good for the imagination.)  Simply phrase it in base 10.  If your need was to have a number that was one less than a multiple of 1000 you'd instantly recognize that as long as the number ended in 999 it didn't matter what digits were to the left of the low-order 999.


Glad that it makes sense now,
Kent
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

26 Experts available now in Live!

Get 1:1 Help Now