[millstone]

So every terminating function is O(1) since your computer has only a finite number of possible states!

The real question is whether the input is big enough that the cost is dominated by the asymptotic behavior, and not the constant coefficient. The O(N) "obvious" algorithm was faster than the O(1) "3 ops 64 bit algorithm," so I think the answer is no, it is not big enough. N=8 sufficiently small that the asymptotic complexity is irrelevant.

[Dylan16807]

I think the logical way to look at algorithmic efficiency starts by picking a reasonable N. "Number of bits in a byte" is something that very rarely changes, and never reaches high values, so it makes a bad N. The flip side of this is that something like "number of bits in main memory" is very flexible and reaches extremely large numbers, so it shouldn't be a constant.

If I wasn't making a point about different methods to flip bits, and I was just naively classifying these byte flippers, I would probably call all of these O(1). Or perhaps O(N) where N is the size of input in bytes.