How get smallest n, that 2 ^ n >= x for given integer x in O(1)?

Question

How for given unsigned integer x find the smallest n, that 2 ^ n ≥ x in O(1)? in other words I want to find the index of higher set bit in binary format of x (plus 1 if x is not power of 2) in O(1) (not depended on size of integer and size of byte).

Answer 1

If you have no memory constraints, then you can use a lookup table (one entry for each possible value of x) to achieve O(1) time.

If you want a practical solution, most processors will have some kind of "find highest bit set" opcode. On x86, for instance, it's BSR. Most compilers will have a mechanism to write raw assembler.