<?xml version="1.0" encoding="UTF-8" standalone="yes"?><oembed><version><![CDATA[1.0]]></version><provider_name><![CDATA[The ryg blog]]></provider_name><provider_url><![CDATA[https://fgiesen.wordpress.com]]></provider_url><author_name><![CDATA[fgiesen]]></author_name><author_url><![CDATA[https://fgiesen.wordpress.com/author/fgiesen/]]></author_url><title><![CDATA[Rounding up to the nearest integer that&#8217;s congruent to k mod&nbsp;N]]></title><type><![CDATA[link]]></type><html><![CDATA[<p>It&#8217;s fairly well-known (among programmers anyway) that say rounding up x to the nearest multiple of 8 can be accomplished using the formula <code>(x + 7) &amp; ~7</code>, and that in general rounding up to the nearest multiple of N (where N is a power of 2) can be accomplished using <code>(x + N - 1) &amp; ~(N - 1)</code>. But sometimes you need a slightly generalized version: round up to the nearest value that is congruent to some <img src="https://s0.wp.com/latex.php?latex=k+%5Cpmod+N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002" srcset="https://s0.wp.com/latex.php?latex=k+%5Cpmod+N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002 1x, https://s0.wp.com/latex.php?latex=k+%5Cpmod+N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002&#038;zoom=4.5 4x" alt="k &#92;pmod N" class="latex" />; for example, this crops up in boundary tag-using memory allocators when the user requests aligned memory. Such allocators put a header before allocated blocks (just before the address returned to the caller). For the user-visible pointer to be aligned by say 32, that header needs to fall at an address that&#8217;s <em>off</em> alignment by a specified distance (which brings us to our problem).</p>
<p>It&#8217;s not immediately obvious how to adapt the original formula to this case (there is a way; I&#8217;ll get to it in a second). Now this is not exactly a frequent problem, nor is there any real need for a clever solution, but it turns out there is a very nice, satisfying solution anyway, and I wanted to write a few words about it. The solution is simply <code>x + ((k - x) &amp; (N - 1))</code> for power-of-2 N. The basic approach works in principle for arbitrary N, but <code>x + ((k - x) % N)</code> will not work properly in environments using truncated division where taking the modulus of a negative argument can return negative results, which sadly is most of them. That said, in the remainder of this short post I&#8217;ll write <code>% N</code> instead of <code>&amp; (N - 1)</code> with a &#8220;N needs to be a power of 2&#8221; disclaimer anyway, since there&#8217;s really nothing about the method that really requires it. Finally, this expression works fine even in overflowing unsigned integer arithmetic when N is a power of 2, but not for non-power-of-2 N.</p>
<p>What I like about this solution is that, once you see it written down, it&#8217;s fairly clear that and why it works (unlike many bit manipulation tricks), provided you know the rules of modular arithmetic: <img src="https://s0.wp.com/latex.php?latex=x+%2B+%28%28k+-+x%29+%5Cbmod+N%29+%5Cequiv+x+%2B+%28k+-+x%29+%3D+k+%5Cpmod+N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002" srcset="https://s0.wp.com/latex.php?latex=x+%2B+%28%28k+-+x%29+%5Cbmod+N%29+%5Cequiv+x+%2B+%28k+-+x%29+%3D+k+%5Cpmod+N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002 1x, https://s0.wp.com/latex.php?latex=x+%2B+%28%28k+-+x%29+%5Cbmod+N%29+%5Cequiv+x+%2B+%28k+-+x%29+%3D+k+%5Cpmod+N&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002&#038;zoom=4.5 4x" alt="x + ((k - x) &#92;bmod N) &#92;equiv x + (k - x) = k &#92;pmod N" class="latex" />. We&#8217;re adding a non-negative value to x, so it&#8217;s clear that the result is &ge; x (provided there is no overflow). And we&#8217;re adding the smallest possible value we can to get to a value that&#8217;s congruent to k (mod N); I wrote about similar things before in my post <a href="https://fgiesen.wordpress.com/2015/09/24/intervals-in-modular-arithmetic/">&#8220;Intervals in modular arithmetic&#8221;</a>.</p>
<p>There&#8217;s an equivalent expression for rounding down to the nearest value congruent to k (mod N): <code>x - ((x - k) % N)</code> that works (and is easy to prove) the same way.</p>
<p>It&#8217;s interesting to consider the case k=0. The round-down variant, <code>x - (x % N)</code>, feels fairly natural and is something I&#8217;ve seen in &#8220;real-world&#8221; code more than once. The round-up variant, <code>x + (-x % N)</code> is something I&#8217;ve never seen anywhere. Once you throw the k in there, it all makes sense, but without it the expression looks quite odd.</p>
<p>Finally, here&#8217;s the aforementioned way to adapt the &#8220;regular&#8221; round-up formula to produce a value that&#8217;s congruent to k (instead of 0) mod N (and we&#8217;re back to requiring power-of-2 N here): <code>((x - k + N - 1) &amp; ~(N - 1)) + k</code>. This uses a different trick from the intervals in modular arithmetic paper: shift the origin around. In this case, we don&#8217;t have a formula for arbitrary k, but we do have a formula to round up to the nearest multiple of N. So we first subtract k; in this new shifted coordinate system, we want to round up to the next-larger multiple of N, which we know how to do. And finally, we add back k. It gets the job done, but it&#8217;s not as pretty as the other variant (in my opinion anyway), and it takes some thinking to convince yourself that it works at all.</p>
]]></html></oembed>