CODEWITHSUNDEEP
c++bit-manipulation
Matt Parkins
Matt Parkins

Reputation: 24708

Move integer to the nearest divisible by 4 in C++

I'd like to move an integer up to the nearest 'divisible by 4' number in C++, but not if the number is currently divisible by 4. Here's my best attempt, but I'm sure this is suboptimal:

offset = (offset & 3) ? (offset | 3) +1 : offset;

There must surely be a fast way of doing this that doesn't include the tertiary IF statement?

Additional note: In this case offset is a 32-bit int.

Upvotes: 9

Views: 1407

Answers (4)

Magnus Hoff
Magnus Hoff

Reputation: 22089

offset = (offset + 3) & ~(decltype(offset))3;

Or

#include <type_traits>
// ...
offset = (offset + 3) &
    ~static_cast<std::remove_reference<decltype(offset)>::type>(3);

if you need to support the possibility that offset is a reference type, such as size_t&. Thanks @BaummitAugen.

It also seems to work when offset is wider than int even without the type cast, offset = (offset + 3) & ~3;, but I am uncertain as to whether or not it is mandated by the language standard.

This algorithm can be described in English as "add 3 then round down".

The rounding down part is done by setting the two least significant bits to zero by binary arithmetics. Unsetting of bits is done by applying binary AND with the inverse bit pattern, in other words we make a bit pattern of all the bits whose value we want to keep unchanged and apply it as a mask.

Binary representation of 3: 00000011

We get the inverse bit mask with the ~ (bitwise NOT, not to be confused with ! logical NOT) operator: ~3

For the ~ operator, the size of the operand determines the size of the result, so on my machine ~(unsigned char)3 == 252 (1111 1100) and ~(unsigned int)3 == 4294967292 (1111 1111 1111 1111 1111 1111 1111 1100). The default size for an integer literal is int.

When offset is a wider type (has more bits) than int, we need the operand to ~ to be widened so the bitmask matches. This is why we cast the literal 3 to the same type as offset.

Upvotes: 9

fredoverflow
fredoverflow

Reputation: 263250

Here is an alternative approach:

offset += -offset & 3;

Depending on the division rest (0, 1, 2, or 3), it adds the appropriate amount to round up (0, 3, 2 or 1).

Upvotes: 2

CashCow
CashCow

Reputation: 31445

offset = ((offset +3 ) >>  2) << 2;

However I prefer Magnus Hoff's solution.

offset should ideally be an unsigned type. If you make this an inline function you can use a parameter that is unsigned. You can also parameterise the power, of course, i.e. 2 in this case. In such a case the number you add would be (1<

So for a general solution:

template< typename U >
U roundUpPower2( U num, size_t nBits )
{
   return (( num + (static_cast<U>(1) << nBits) - 1 ) >> nBits) << nBits;
}

Using a bitmask rather than two shits

template< typename U >
U roundUpPower2( U num, size_t nBits )
{
   U mask = (static_cast<U>(1) << nBits) - 1;
   return (num + mask) & ~mask;
}

Note the purpose of casting the 1 is that if you are using 64 bit arithmetic your nBits might be any value from 1 to 63 and plain 1 is of type int, signed and probably 32 bits, in which case the arithmetic would go wrong if nBits is 32 or higher if you don't cast it.

Upvotes: 4

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171167

You can do this:

number = 4 * ((number + 3) / 4)

Whether it's more efficient depends on your setup - profile and see.

Upvotes: 3

Related Questions