mrwad99
asked on
Binary OR operator confusion!
Ah hello.
This is a very short question. I have the following code:
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
x does not get rounded the nearest multiple of 32!
Can someone please explain this?
TIA
This is a very short question. I have the following code:
int n = /* some value */
int x = n | 0x1F; // 31
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
x does not get rounded the nearest multiple of 32!
Can someone please explain this?
TIA
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.
Visualised...
010101
011111
------
011111
010101
100000
------
110101
> 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
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
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
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
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
>> 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:
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.
"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;
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);
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
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
ASKER
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.
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.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
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
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
Sara
ASKER
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?
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?
>> 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.
That's something that Kdo's previous post explains quite well.
ASKER
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...
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
> 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 */
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 */
ASKER
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.
"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.
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
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