Search code examples
symbolstaocp

What does the acronym or shorthand "lg" mean?

What does "lg" mean in the following phrase?

"... we ignore the least significant lg t bits of x when referring to Mt[x]." (Knuth, 2005, pp. 4-5).

From the context, it seems like "lg t" means "t -1" so that lg 2 would be 1 and lg 5 would be 4. That said, what is the strict meaning of "lg" here?

References

Knuth, D. E. (2005). The art of computer programming: Volume 1, fascicle 1 : MMIX, a RISC computer for the new millennium. Upper Saddle River, New Jersey: Addison-Wesley.

Solution

  • lg means log to the base 2.

    i.e. lg(4) = 2, lg(2) = 1.