Add significant bits/fastLog2 operation for BigInts

[dlesnoff]

In order to improve modular exponentiation or to write other higher-order functions (functions that do not rely on BigInts internal representation), we might want to count the number of significant bits (bits after leading zeros, without the sign bit in complement representation of signed integers) or at least the logarithm in base 2 of the number.

We can determine the number of significant bits from the logarithm in base 2 as:
significantBits(n) = floor(log_2(n)) + 1

func significantBits*(n: BigInt): int =
  if n < 0:
    return significantBits(-n)
  fastLog2(n.limbs.high) + 32*(n.limbs.len-1)

How would you optimize the negative case ? Can we just take the two’s complement of the highest limb and then compute the fastLog2(n.limbs.high) ?

func significantBits*(n: BigInt): int =
  var highest_limb = n.limbs.high
  if n < 0:
    highest_limb = not n.limbs.high + 1
  fastLog2(highest_limb) + 32*(n.limbs.len-1)

[konsumlamm]

I think you're misunderstanding how negative BigInts are stored. Negating a BigInt is just inverting the isNegative flag, nothing is stored in two's complement.