Statement about least significant bits in the next field of a linked list in C
bit-manipulation, c, data-structures, pointers
Solution
Many processor architectures are designed so that operations are supposed to be performed on word-aligned addresses. For example, some 32-bit processors are designed so that any word operation must be done at addresses that are multiples of 4 bytes (32 bits), such as addresses 0, 4, 8, 12, 16, 20, etc. Similarly, some 64-bit processors only allow word operations to be done at addresses that are multiples of 8 bytes. This has various advantages in hardware, such as being able to more easily detect if two different instructions refer to the same word in memory, which makes the processor faster. In some processors, you'll get a bus error if you try to do a nonaligned read, while in others it's legal to do so but the performance will be significantly degraded.
Because of this, most memory allocation libraries are designed so that they align all allocations at word boundaries. This means that on a 32-bit system, the two low-order bits of the address will be 0 (because the number is a multiple of four) and on a 64-bit system the three low-order bits of the address will be 0. Many data structures compress their representations by using these low-order bits to store extra information. For example, some implementations of red/black trees will place the bit that stores whether a node is red or black into the low order bits of one of the pointers, and some AVL trees (which need to store two bits of information) will pack those bits into the low-order bits of these pointers. Some garbage collection algorithms use similar techniques to store mark bits.
EDIT: In C, some compilers support a `uintptr_t` type that represents an integer large enough to hold a pointer. You can cast the pointer to a `uintptr_t` and then use standard bitwise operators on the `uintptr_t` variable to set or clear the bits, then cast back to a pointer to store the result. In C++, to the best of my knowledge, this would produce undefined behavior.
Hope this helps!
Problem
I found the following statement about the least significant bits in the next field of a linked list in C: "In C, the next field is a pointer. For performance reason related to memory subsystem on a processor, memory is allocated on word boundaries, and (at least) two least significant bits in the next pointers are 0." Is this true? I can't understand why so if so. Please help.