Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Binary OR operator confusion!

Posted on 2011-02-14
19
Medium Priority
?
393 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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 31

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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 46

Expert Comment

by:Kent Olsen
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 35

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 100 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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 100 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 46

Expert Comment

by:Kent Olsen
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 35

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 46

Accepted Solution

by:
Kent Olsen earned 300 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 46

Expert Comment

by:Kent Olsen
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

Tech or Treat!

Submit an article about your scariest tech experience—and the solution—and you’ll be automatically entered to win one of 4 fantastic tech gadgets.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
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 the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

636 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