-1

What does & ~(minOffsetAlignment - 1) mean?

Does it mean address of destructor?

This is the code snippet I got it from.

VkDeviceSize is uint64_t.

VkDeviceSize getAlignment(VkDeviceSize instanceSize, VkDeviceSize minOffsetAlignment) 
{
    if (minOffsetAlignment > 0) 
    {
        return (instanceSize + minOffsetAlignment - 1) & ~(minOffsetAlignment - 1);
    }
    return instanceSize;
}
phuclv
  • 37,963
  • 15
  • 156
  • 475
Jonh Smith Benjamin
  • 49
  • 8
  • 4
    `~` is Unary complement (bit inversion) – drescherjm Jan 04 '22 at 03:21
  • 2
    lookup bitwise operations – NathanOliver Jan 04 '22 at 03:21
  • `&` means bitwise-AND, as it is used as a binary operator. It would only mean "address-of" if it had been used as a unary operator. – Andreas Wenzel Jan 04 '22 at 03:26
  • See [arithmetic operators](https://en.cppreference.com/w/cpp/language/operator_arithmetic). – WhozCraig Jan 04 '22 at 03:32
  • Related: [Bit Twiddling Hacks](https://graphics.stanford.edu/~seander/bithacks.html) – John Kugelman Jan 04 '22 at 03:35
  • 1
    The `~(minOffsetAlignment - 1)` part can also be written as `-minOffsetAlignment`, if you understand what negation does that may be a bit simpler, but almost no one understands what negation does – harold Jan 04 '22 at 03:37
  • Welcome to the world of limited character sets - some characters do multiple duties. `~` means destructor in one context, but bit inversion in another. – Mark Ransom Jan 04 '22 at 03:37
  • @harold that's only true if the arithmetic is using two's complement. I'll admit that it's hard to find anything that isn't two's complement, but I learned on a machine that was one's complement and I never forget. – Mark Ransom Jan 04 '22 at 03:39
  • @MarkRansom fortunately `VkDeviceSize` is unsigned, so two's complement negation is the only option – harold Jan 04 '22 at 03:41
  • @harold I missed that little detail, thanks. But I think what you mean is that negation is impossible? Meaning the bit manipulation sequence given in the question is the only option. – Mark Ransom Jan 04 '22 at 03:44
  • It's possible to understand `&~` as "set subtraction", since it returns a copy of the LHS with all bits on the RHS unset. – o11c Jan 04 '22 at 03:47
  • @MarkRansom no not at all, it being unsigned does not prevent negation: it makes negation safe and well-defined, the only meaning it can have is two's complement negation and there is no UB either (both of which are false for signed negation). It's ironic really, it's better to negate an unsigned integer than a signed one. – harold Jan 04 '22 at 03:52
  • @harold that must be a really obscure corner of the spec that defines that operation then. Because it's logically impossible to create a negative number in an unsigned type. – Mark Ransom Jan 04 '22 at 03:59
  • @MarkRansom well it's in [expr.unary.op], "The negative of an unsigned quantity is computed by subtracting its value from 2^n, where n is the number of bits in the promoted operand", the only way to make that true is to use two's complement negation for unsigned integers, even on a machine that uses ones' complement (or something else) for signed negation. It preserves that `x + (-x) == 0` (with unsigned addition, wrapping modulo 2^n) so it's not just some arbitrary thing, though admittedly unsigned negation seems pretty weird at first – harold Jan 04 '22 at 04:11

3 Answers3

5

It's a common trick to align a certain number to a certain boundary. It assumes that minOffsetAlignment is a power of two.

If minOffsetAlignment is a power of two, its binary form will be a one followed by zeros. For example if 8, the binary will be b00001000.

If you subtract one, it will become a mask where all the bits that can be changed will be flagged as one. For the same example, it will be b00000111 (all numbers from 0 to 7).

If you take the complement of this number, it becomes a mask for clearing. In the example, b11111000.

If you AND (&) any number against this mask, it will have the effect to zero all the bits relative to numbers below the alignment.

For example, say I have the number 9 b00001001. Doing 9&7 is b00001001 & b11111000 which results in b00001000 or 8.

The resulting value is the computed value aligned for the given amount.

  • Oh, thank you. The tilde ~ is a NOT logic gate? It turns b00000000 into b11111111? – Jonh Smith Benjamin Jan 28 '22 at 18:02
  • @JonhSmithBenjamin It's the bitwise NOT operator https://www.arduino.cc/reference/en/language/structure/bitwise-operators/bitwisenot/ –  Jan 28 '22 at 18:14
1

What does &~ mean?

In this case, & is the bitwise and operator. It is a binary operator. Each bit of the result is set if the corresponding bit is set for both operands, otherwise the bit is unset. In this case, the left hand operand is (instanceSize + minOffsetAlignment - 1) and the right hand operand is ~(minOffsetAlignment - 1)

~ is the bitwise not operator. It is a unary operator. Each bit of the result is set if the corresponding bit is unset in the operand, otherwise the bit is unset. In this case, the operand is (minOffsetAlignment - 1)

eerorika
  • 232,697
  • 12
  • 197
  • 326
1

The idea of this code is to say, "Given a particular (object) instance size, how many bytes of memory are used if the allocator has to round-up object sizes to some power-of-two multiple." Note that if the instance size is already a multiple of the power of two (e.g. 8), then no rounding-up is needed.

It is often the case that memory needs to be allocated in multiples of the hardware's word size in bytes. On a 32-bit platform that would mean a multiple of 4, on 64-bit, a multiple of 8. Note however that the multiple (and thus minOffsetAlignment) must be a power of 2 (the author of this code, for better or worse, is 100% assuming the person calling this function knows this).

Let's assume for the rest of my answer that we're working with a hardware word size of 64-bit, and that our platform must allocate memory in chunks of 8 bytes (64 bits divided by 8 bits per byte == 8 bytes). So minOffsetAlignment will be passed as 8.

Consequently, if the instance size is 1-8 bytes, our function must return 8. If it's 9-16 bytes, it must return 16, and so on.

This answer shows how to round up a value to some nearest integer provided the value being rounded isn't already a multiple of that integer.

In the case of rounding up to the nearest multiple of 8, the procedure is to add 7, then do integer division to divide by 8, then multiply by 8.

So:

(0 + 7) / 8 * 8 == 0 // a zero-byte instance requires zero memory bytes

(1 + 7) / 8 * 8 == 8 // a one-byte instance requires eight memory bytes
(2 + 7) / 8 * 8 == 8 // a two-byte instance requires eight memory bytes
...
(8 + 7) / 8 * 8 == 8 // an eight-byte instance requires eight memory bytes

(9 + 7) / 8 * 8 == 16 // a nine-byte instance requires sixteen memory bytes
...

What the code in your question is doing is exactly the above algorithm, but it's using bitwise operations instead of addition, division, and multiplication which on some hardware is faster.

Now, how does it do this?

First we have to get the (instanceSize + 7) part. That's here:

(instanceSize + minOffsetAlignment - 1)

Then we have to divide it by 8, truncate the remainder, and multiply the result of the division by 8.

The last part does that all in one step, and this explains why minOffsetAlignment had to be a power of two.

First, we see:

minOffsetAlignment - 1

If minOffsetAlignment is 8, then its binary value is 0b00001000.

Subtracting 1 from 8 gives 7, which in binary is 0b00000111.

Now the complement of 7 is taken:

~(minOffsetAlignment - 1)

This inverts all the bits so we get ...1111000 (for a 64-bit integer such as VkDeviceSize there are 61 leading 1's and 3 trailing 0's).

Now, putting the whole statement together:

(instanceSize + minOffsetAlignment - 1) & ~(minOffsetAlignment - 1)

We see the & operator will clear the last three bits of whatever the result of (instanceSize + minOffsetAlignment - 1) is.

This forces the return value to be a multiple of 8 (since any binary integer with the last three bits 0 is a multiple of 8), but given that we already added 7 it also rounded it up to the nearest multiple of 8 provided instanceSize wasn't already a multiple of 8.

par
  • 17,361
  • 4
  • 65
  • 80