What is the mathematical principle of buddy algorithm? The buddy algorithm is:


  The buddy for any block of size $2^k$ is another block of the same size, and with the same page frame number except that the kth bit is reversed.


Example:

If the block size if $2^3$ and the start page frame number(aka pfn) of this block is 0xC, the page frame number of the buddy of this block is pfn=0x4.

This algorithm is very ingenious but I have two questions.


Why the buddy of 0xC is 0x4 instead of 0x14?
Why reversing the kth bit does the trick?


References:
http://research.cs.vt.edu/AVresearch/MMtutorial/buddy.php
The buddy algorithm is just treating your memory of size $2^K$ as a binary tree where the root is the entire memory, and each node of size $2^k$ has two children which are the two equal size subblocks of size $2^{k-1}$.

The buddy system restricts you to only splitting a node into its two children (which are then the two buddies), or taking two buddies and coalescing them into their parent.  This restriction is put in place entirely to enable the cute/ingenious trick of identifying your buddy by flipping the $k$th bit.

Other than being cute, there is very little to recommend buddy systems as memory allocators.  More general systems that allow you to coalesce with any neighbor, even if it's not your buddy, are slightly more expensive to compute per deallocation, but result in much less internal and external  fragmentation in practice.