CODEWITHSUNDEEP
cmath
idealistikz
idealistikz

Reputation: 1267

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

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

Upvotes: 7

Views: 2522

Answers (6)

paxdiablo
paxdiablo

Reputation: 881623

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 26 = 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.

Upvotes: 17

Alexander Malakhov
Alexander Malakhov

Reputation: 3529

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

Upvotes: 3

icio
icio

Reputation: 3138

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;

Upvotes: 5

AnT stands with Russia
AnT stands with Russia

Reputation: 320531

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.

Upvotes: 2

Plynx
Plynx

Reputation: 11461

For unsigned ints

return 0

For signed ints

return floor(-MAXINT/64)*64

;-)

Upvotes: 1

Jeff Kelley
Jeff Kelley

Reputation: 19071

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

Upvotes: 1

Related Questions