Round an integer to the nearest int that is lower than or equal to it and a multiple of 64

Question

Given an integer x, how would you return an integer y that is lower than or equal to x and a multiple of 64?

Answer 1

Simply and it with the bit inversion of (64-1):

x = x & ~63
// 64  is 000...0001000000
// 63  is 000...0000111111
// ~63 is 111...1111000000

This basically clears out the lower six bits which is the same as rounding it down to a multiple of 64. Be aware that this will round towards negative infinity for negative numbers, not towards zero, but that seems to be what your question requires.

You can see the behaviour here in this multiple-of-four variant:

#include <stdio.h>
int main (void) {
    int i;
    for (i = -10; i <= 10; i++) {
        printf ("%3d -> %3d\n", i, i & ~3);
    }
    return 0;
}

This produces:

-10 -> -12
 -9 -> -12
 -8 ->  -8
 -7 ->  -8
 -6 ->  -8
 -5 ->  -8
 -4 ->  -4
 -3 ->  -4
 -2 ->  -4
 -1 ->  -4
  0 ->   0
  1 ->   0
  2 ->   0
  3 ->   0
  4 ->   4
  5 ->   4
  6 ->   4
  7 ->   4
  8 ->   8
  9 ->   8
 10 ->   8

---

Keep in mind this only works for powers of two (like 2⁶ = 64) and two's complement (the ISO standard doesn't mandate that representation - see here for details - but I've never seen an C environment that doesn't use it and I've worked on systems from the puniest 8051 to the largest mainframes). If you want to use any other number for the divisor, you should probably use the proper math functions like floor.

Answer 2

Where x is the number you wish to round down to the nearest multiple of n, the method that you need is:

floor(x / n) * n

which you can implement really nicely in C++ (as opposed to C):

int n = 5;
for (int x = 0; x < 100; x++)
    cout << x << " -> " << (x / n) * n << endl;

Answer 3

(x >> 6) << 6
First shifting 6 bits right, then left - lower bits filled with nulls.
No problems with sign

EDIT : I think most compilers will optimize x / 64 * 64 (and any divide / multiply with small powers of 2) to the same code, so there is no actual need in such bit magic, until you want your code to look really cool :)

(And AndreyT thinks there are even better optimizations for straightforward code, read comments to his post)

Answer 4

Assuming that you need the nearest such integer and that you are working with positive numbers:

x = x / 64 * 64;

Various bit hacks look intreresing, but there's absolutely no need for them in this specific case.

Answer 5

int y = x;
while ( y % 64 )
    y--;

Answer 6

For unsigned ints

return 0

For signed ints

return floor(-MAXINT/64)*64

;-)