# 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.

1. Why the buddy of 0xC is 0x4 instead of 0x14?
2. Why reversing the kth bit does the trick?
• I think that your example is incorrect - starting point of block with size 2^n should be aligned to 2^n. Then, reversing the n'th bit of that address, you will find its buddy, and together they form block of size 2^(n+1) – Bulat Aug 28 '18 at 21:45
• en.wikipedia.org/wiki/Buddy_memory_allocation – Bulat Aug 28 '18 at 21:46

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.