Adding isPowerOf2 to BinaryInteger

Evolution Pitches
38

Well, me neither, but let's explore a bit...

Looking at the bit pattern, I think there's one precheck you could use to fail early when checking for base 10:

var perhapsIsPowerOf10: Bool {
  let exponent = trailingZeroBitCount // see details below
  return (self >> exponent) & 0b1111 == ((exponent << 2) | 0b01) & 0b1111
}
Details

Some observations for the binary pattern for powers of 10 (separated into columns below):

  • Column 1 is some "gibberish"
  • Column 2 is always the last two bits of the exponent
  • Column 3 is always 01
  • Column 4 is the trailing zeros, always in equal number to the exponent value
10^0                                                 1
10^1                                              1_01_0
10^2                                           1_10_01_00
10^3                                         111_11_01_000
10^4                                      100111_00_01_0000
10^5                                    11000011_01_01_00000
10^6                                  1111010000_10_01_000000
10^7                               1001100010010_11_01_0000000
10^8                             101111101011110_00_01_00000000
10^9                           11101110011010110_01_01_000000000
10^10                       10010101000000101111_10_01_0000000000
10^11                     1011101001000011101101_11_01_00000000000
10^12                   111010001101010010100101_00_01_000000000000
10^13                100100011000010011100111001_01_01_0000000000000
10^14              10110101111001100010000011110_10_01_00000000000000
10^15            1110001101011111101010010011000_11_01_000000000000000
10^16         1000111000011011110010011011111100_00_01_0000000000000000
10^17       101100011010001010111100001011101100_01_01_00000000000000000
10^18     11011110000010110110101100111010011101_10_01_000000000000000000

So the algorithm is to look at the number of trailing zeros to get the exponent. Then we make sure column 2 matches the last two bits of the exponent and column 3 matches 0b01. Since column 1 is left unchecked, we don't know for sure we have a power of 10.

But do we have a fast way to compute a power of 10? Since we can easily find the exponent from the bit pattern we could just compute 10^exponent and that'd give us an exact result to check for. That'd be better than just knowing you may have a power of 10.

There aren't that many powers of 10 that can fit in 64 bits anyway. Let's make a lookup table with 20 entries that'll give us a very quick check for powers of 10 in the 64-bit range. Some other algorithm can be used above that.

Full implementation (fast path up to 64-bit) 
var isPowerOf10: Bool {
	let exponent = trailingZeroBitCount
	switch exponent {
	case 0:  return self == 1 as UInt8
	case 1:  return self == 10 as UInt8
	case 2:  return self == 100 as UInt8
	case 3:  return self == 1000 as UInt16
	case 4:  return self == 10000 as UInt16
	case 5:  return self == 100000 as UInt32
	case 6:  return self == 1000000 as UInt32
	case 7:  return self == 10000000 as UInt32
	case 8:  return self == 100000000 as UInt32
	case 9:  return self == 1000000000 as UInt32
	case 10: return self == 10000000000 as UInt64
	case 11: return self == 100000000000 as UInt64
	case 12: return self == 1000000000000 as UInt64
	case 13: return self == 10000000000000 as UInt64
	case 14: return self == 100000000000000 as UInt64
	case 15: return self == 1000000000000000 as UInt64
	case 16: return self == 10000000000000000 as UInt64
	case 17: return self == 100000000000000000 as UInt64
	case 18: return self == 1000000000000000000 as UInt64
	case 19: return self == 10000000000000000000 as UInt64
	default:
		// if this is 64-bit or less we can't have a higher power of 10
		if self.bitWidth <= 64 { return false }
		// fail early it not matching the easy-to-check bit pattern
		if !self.perhapsIsPowerOf10 { return false }
		// now time for the slow path
		return self._isPower(of: 10)
	}
}

Note: Beyond 64 bits, the performance characteristics will be uneven.

Generalizing for all bases multiple of 10

You can also generalize the code above to other bases that are a multiple of 10 by adding a precheck of the base-10 exponent found in the bit pattern:

func isPower(ofMultipleOf10 base: Int) -> Bool {
	precondition(base.isMultiple(of: 10))
	let exponentOf10 = trailingZeroBitCount // exponent for base 10
	let exponentOfBase = base.trailingZeroBitCount
	if !exponentOf10.isMultiple(of: exponentOfBase) { return false }
	return self.isPowerOf10
}
3 Likes