[lucio]

>Why eight steps? Well, to differentiate between 256 equally likely possibilities requires eight bits. Each experiment, since it differentiates between two equally likely outcomes (pass and fail), provides one bit of information. Therefore, we need eight such experiments to give us the eight bits we need to determine the faulty optimization.

Is this explanation a little odd?

Each step in a binary search halves the amount of suspects, you need 8 steps because with 8 steps you go from 256 suspects to one.

I can't see it the way the article describes it.

It's just me? Anyone else found the article reasoning for 8 steps a little odd?

[winceschwab]

Yeah, I noticed that too. Treating a byte as eight tally marks misses the point about the combinatorialnature of place settings.

It's not 100% wrong, because bit shifting and bit packing are real-world applications used in memory all the time.

But these are not the only possible values:

  00000001
  00000010
  00000100
  00001000
  00010000
  00100000
  01000000
  10000000

It's not incorrect to make a decision to limit one's input to those values, but it is incorrect to presume that binary data can only be recorded that way.

Treating those 8 place settings as eight lightbulb circuits that each need an individual test isn't the right mindset for someone performing compiler optimization.