How to calculate integer logarithm of base 3, using fast bit operations?

Question

Calculating of integer logarithm base 2 is pretty easy in near any computer language - you just find the largest '1' in binary representation, and rest becomes zero.

Is is possible to do the same fast trick for other bases, for example 3, - calculate logarithm of base 3 or get the nearest integer from below what is correct 3ⁿ?

Answer 1

Yes, using the same method as Find integer log base 10 of an integer we can achieve the same thing. We just replace powers of 10 with powers of 3, log₁₀2 with log₃2, and a multiplication of 1/log₃2 ? ³²³???? is used

Here's a simple PoC in JavaScript that you can try live on the browser. See the function ilog3

const POW3 = new Int32Array([ 1, 3, 9, 27, 81, 243, 729,
  2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969,
  14348907, 43046721, 129140163, 387420489, 1162261467 ])

function ilog2(x) {
  // Here floating-point log is used because JavaScript doesn't have
  // find-first-set/count-leading-zero/integer-log-2/whatever
  // to get the position of the most significant bit. 
  // On platforms/languages with that feature we should use that instead
  return Math.trunc(Math.log2(x))
}

function ilog3(x) {
  let t = (ilog2(x) + 1)*323 >>> 9
  return t - (x < POW3[t])
}

allOK = true
const Log3 = Math.log(3)
function check(x) {
  a = ilog3(x);
  b = Math.trunc(Math.log(x)/Log3);
  if (a != b) {
    console.log([x, a, b])
    allOK = false
  }
}

function checkAll(x) {
  if (x > 1) { check(x - 1) }
  check(x)
  check(x + 1)
}

POW3.forEach(checkAll)
if (allOK) { console.log("OK") }