-1

When I browsing c++ header files of opencv, It happened to see the construct (ptr + n-1) & -n in alignPtr function. The complete function as follows

/*!
  Aligns pointer by the certain number of bytes

  This small inline function aligns the pointer by the certain number of bytes by shifting
  it forward by 0 or a positive offset.
*/
template<typename _Tp> static inline _Tp* alignPtr(_Tp* ptr, int n=(int)sizeof(_Tp))
{
    return (_Tp*)(((size_t)ptr + n-1) & -n);
}

Can you explain how it works?

Jobin
  • 6,506
  • 5
  • 24
  • 26
  • 1
    This small inline function aligns the pointer by the certain number of bytes by shifting it forward by 0 or a positive offset. – erip Jun 06 '16 at 12:18
  • @erip this is very funny indeed, though the question is quote, "how it works", end of quote. – bereal Jun 06 '16 at 12:20
  • 1
    @bereal I noticed it after posting. I'm not funny. – erip Jun 06 '16 at 12:21
  • you can find out by looking at what happens with the bit patterns when doing this calculation. Note that you'll need `n` to be a power of 2 for this to work. – Sander De Dycker Jun 06 '16 at 12:24
  • Unfortunately, it is not possible to fully explain how binary and two-complement's arithmetic works, in a short answer to stackoverflow.com. Go buy an introductory book on computer programming, which should explain this in detail. That's the best answer for you. – Sam Varshavchik Jun 06 '16 at 12:24
  • This function is very poor, since it will fail for `n` not a power of two, which may easily happen for some types `_Tp`. – Walter Jun 06 '16 at 12:38

1 Answers1

1

In this expression its implicit that n is a power of 2 such as 2, 4, 8 etc. Lets say that n is 2^m

In a twos complement binary system:

  • -2 is ...11110
  • -4 is ...11100
  • -8 is ...11000

In general, n = -2^m has a representation with exactly the m rightmost digits being zero.

This means, if we take any number and & it with -2^m then it will be returned with the m rightmost digits being zero, and the other digits retained, which makes the answer a multiple of 2^m.

This means the expression x & -2^m will effectively "floor" the number to the largest multiple of 2^m that is less than or equal to x.

The addition of (n - 1) that is being done:

(x + (n-1)) & -2^m

effectively changes this from a "floor" to a "rounding".

donkopotamus
  • 22,114
  • 2
  • 48
  • 60