# Adding isPowerOf2 to BinaryInteger

**URL:** <https://forums.swift.org/t/adding-ispowerof2-to-binaryinteger/24087>\
**Category:** Pitches\
**Created:** [May 3, 2019, 6:03am UTC](https://forums.swift.org/t/adding-ispowerof2-to-binaryinteger/24087 "2019-05-03T06:03:59Z")\
**Posts on this page:** 1\
**Showing post:** 38

<div class="post-metadata">

**Author:** ![michelf](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/michelf/32/1180_2.png) [@michelf](https://forums.swift.org/u/michelf)\
**Post date:** [May 9, 2019, 10:47am UTC](https://forums.swift.org/t/adding-ispowerof2-to-binaryinteger/24087/38 "2019-05-09T10:47:35Z")

</div>

> [@dingobye](#):
>
> I am thinking of if we should also have a dedicated optimization when base is 10, which may be a bit more commonly used. However, I am not aware of any efficient implementation in this case.

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:

```swift
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
> 
> ```swift
> 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)**
>
> ```swift
> 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:
> 
> ```swift
> 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
> }
> 
> ```

---

_[View the full topic](https://forums.swift.org/t/adding-ispowerof2-to-binaryinteger/24087)._