[NSWI004] Note on is_power_of_two

[Miroslav Hrabal]

I might as well try to explain why I believe this trick should work, I will only take unsigned numbers into account:
Let's say we have a number `x`, written in its binary representation (let's say 32bit, so that all our numbers have 32 digits). There are three possible situations which can occur:

1) all digits are zeroes, so `x` is zero (special case, we handle this separately)
2) all digits except a single one are zeroes, meaning `x` is a power of two
3) at least two digits are ones, meaning `x` is not a power of two

Now, case 1 is handled separately, so we only need to take 2 and 3 into account. Imagine what happens when you subtract 1 from `x` in these cases:

case 2) the single non-zero digit becomes zero and all the lower digits change to ones, meaning (x & (x-1)) = 0
e.g. 0b1000 - 0b0001 = 0b0111, 0b1000 & 0b0111 = 0b0000

case 3) the highest non-zero digit will never change, meaning (x & (x-1)) > 0. You can see this if you try binary subtraction by 1 on paper - propagation of a carry bit stops at the lowest non-zero digit (and there are at least two)
e.g. 0b1010 - 0b0001 = 0b1001, 0b1010 & 0b1001 = 0b1000

I hope I made no major mistakes here.

Sincerely,

Miroslav Hrabal


---------- Původní e-mail ----------

Od: Miroslav Hrabal <MHN at email.cz>

Komu: Operating Systems Course <nswi004 at d3s.mff.cuni.cz>

Datum: 5. 1. 2021 1:07:51

Předmět: Re: [NSWI004] Note on is_power_of_two

Greetings,


I don't think your counterexample here is valid as 3 = 0b11 and not 0b101 (= 5).


Sincerely,


Miroslav Hrabal






---------- Původní e-mail ----------

Od: Thomas Mol <thomasfolkertmol at gmail.com>

Komu: Operating Systems Course <nswi004 at d3s.mff.cuni.cz>

Datum: 5. 1. 2021 0:43:29

Předmět: [NSWI004] Note on is_power_of_two

Good night,

The trick used in the is_power_of_two inline looks nice, but it's not
actually valid. For example, 3 has no common bits with 3 - 1 (0b101
and 0b010).
Is there a particular reason our frame allocator should only allocate
powers of two anyway?

Best regards,
Thomas Folkert Mol
_______________________________________________
NSWI004 mailing list
NSWI004 at d3s.mff.cuni.cz
https://d3s.mff.cuni.cz/mailman/listinfo/nswi004
_______________________________________________
NSWI004 mailing list
NSWI004 at d3s.mff.cuni.cz
https://d3s.mff.cuni.cz/mailman/listinfo/nswi004