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?

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.

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

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Kent OlsenData Warehouse Architect / DBACommented:

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.

>> 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:

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);

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.

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.

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); } }

30: x = 32 y = 3231: x = 32 y = 3232: x = 64 y = 3233: x = 64 y = 6434: x = 64 y = 6435: x = 64 y = 6436: x = 64 y = 6437: x = 64 y = 6438: x = 64 y = 6439: x = 64 y = 6440: x = 64 y = 6441: x = 64 y = 6442: x = 64 y = 6443: x = 64 y = 6444: x = 64 y = 6445: x = 64 y = 6446: x = 64 y = 6447: x = 64 y = 6448: x = 64 y = 6449: x = 64 y = 6450: x = 64 y = 6451: x = 64 y = 6452: x = 64 y = 6453: x = 64 y = 6454: x = 64 y = 6455: x = 64 y = 6456: x = 64 y = 6457: x = 64 y = 6458: x = 64 y = 6459: x = 64 y = 6460: x = 64 y = 6461: x = 64 y = 6462: x = 64 y = 6463: x = 64 y = 6464: x = 96 y = 6465: x = 96 y = 9666: x = 96 y = 96

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.

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).

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?

Kent OlsenData Warehouse Architect / DBACommented:

>>"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.

"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.

Kent OlsenData Warehouse Architect / DBACommented:

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

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.