SE-0288 | Swift Evolution↗

Adding `isPower(of:)` to `BinaryInteger`

Proposal: SE-0288↗
Authors: Ding Ye
Review Manager: Joe Groff
Status: Previewing

01 何が問題だったのか

整数が「ある基数のべき乗かどうか」を判定したい場面は、科学計算やエンジニアリング、信号処理、画像・動画処理、コンパイラの内部処理など幅広い領域で現れます。特に「2 のべき乗かどうか」の判定は定番で、ハッシュテーブルのバケット数チェックなどで頻繁に登場します。

しかし Swift の標準ライブラリには、この用途にそのまま使える API がありませんでした。そのため利用者は古典的なビット演算イディオムを自分で書く必要があります。

// bucketCount が 2 のべき乗であることを要求する
_internalInvariant(
    bucketCount > 0 && bucketCount & (bucketCount - 1) == 0,
    "bucketCount must be a power of two"
)

このコードには次のような課題がありました。

可読性が低い

n > 0 && n & (n - 1) == 0 というイディオムは効率的ではあるものの、ぱっと見て「2 のべき乗判定」だと分かる人は限られます。そのためコメントやエラーメッセージで意図を補足する必要があり、コードが冗長になります。

効率の悪い自前実装が書かれがち

イディオムを知らない利用者が、popcount 系の命令（nonzeroBitCount など）を使った実装を書くこともあります。ハードウェアが popcount 命令をサポートしていない環境では高コストになり、標準的なビット演算版より遅くなることもあります。

型ごとに重複実装されがち

BinaryInteger という抽象に慣れていない利用者は、Int 用・UInt 用と型ごとにほぼ同じ実装を書き分けてしまいがちです。

func _isPowerOf2(_ x: UInt) -> Bool { /* 実装 */ }
func _isPowerOf2(_ x: Int)  -> Bool { /* ほぼ同じ実装 */ }

発見しにくい

既存の isMultiple(of:) のような整数判定 API と並ぶ標準 API がないため、IDE の補完にも現れず、利用者が「そもそもそんな判定を簡潔に書ける方法があるのか」に気付きにくい状況でした。

なお、2 以外の基数（たとえば 4 や 10）のべき乗判定も、FFT のサイズ判定などで実用上使われる場面があります。

02 どのように解決されるのか

BinaryInteger プロトコルに拡張メソッド isPower(of:) を追加します。self が base のべき乗であるときに true を返す、汎用的な判定 API です。

extension BinaryInteger {
    @inlinable public func isPower(of base: Self) -> Bool {
        // 実装は後述
    }
}

意味論

x.isPower(of: base) は次のいずれかが成り立つとき true を返します。

x == 1（任意の基数の 0 乗は 1）
x が 1 個以上の base の積で表せる

BinaryInteger レベルで定義されているため、Self が符号付き型のときは負の値も正しく扱われます。

let x: Int = Int.random(in: 0..<288)
1.isPower(of: x)      // true （x の 0 乗は 1）
1000.isPower(of: 10)  // true （10 の 3 乗）
(-1).isPower(of: 1)   // false
(-32).isPower(of: -2) // true  （(-2) の 5 乗）

これにより、冒頭の例は次のように簡潔になります。

_internalInvariant(bucketCount.isPower(of: 2))

実装方針: fast path / slow path

実装はよく使われる基数に対する fast path と、任意基数に対する汎用的な slow path の組み合わせで構成されます。

extension BinaryInteger {
  @inlinable public func isPower(of base: Self) -> Bool {
    // 頻出する基数は専用の最適化ルートへ
    if base == 2  { return self._isPowerOfTwo }
    if base._isPowerOfTwo { return self._isPowerOf(powerOfTwo: base) }
    if base == 10 { /* 10 専用の最適化 */ }
    // それ以外は汎用実装
    return self._slowIsPower(of: base)
  }
}

base が定数かつ Self が組み込み整数型のような単純な型であれば、コンパイラが定数畳み込みと simplify-cfg により分岐を消去できるため、isPower(of: 2) のような呼び出しは専用ルートを直接呼んだのと同等の性能になることが期待できます。

2 のべき乗判定

2 のべき乗は最重要ケースです。BinaryInteger は任意精度の整数にも適合しうるため、self & (self - 1) == 0 のような演算を丸ごと行うと、演算が複数ワードにまたがる型では高コストになります。そこで words を介したワード単位の実装が採用されます。

extension BinaryInteger {
  @inlinable internal var _isPowerOfTwo: Bool {
    let words = self.words
    guard !words.isEmpty else { return false }

    // 1 ワードで表せる値は古典的イディオムを使う
    if words.count == 1 {
      return self > 0 && self & (self - 1) == 0
    }

    // 符号付きで負なら false（最上位ワードだけ見ればよい）
    if Self.isSigned && Int(bitPattern: words.last!) < 0 {
      return false
    }

    // 非ゼロワードがちょうど 1 つで、そのワードが 2 のべき乗かを確認
    var found = false
    for word in words {
      if word != 0 {
        if found || word & (word - 1) != 0 { return false }
        found = true
      }
    }
    return found
  }
}

基数自身が 2 のべき乗のとき

基数が 4, 8, 16… のように 2 のべき乗なら、trailingZeroBitCount を使って軽量に判定できます。

extension BinaryInteger {
  @inlinable internal func _isPowerOf(powerOfTwo base: Self) -> Bool {
    _precondition(base._isPowerOfTwo)
    guard self._isPowerOfTwo else { return false }
    return self.trailingZeroBitCount.isMultiple(of: base.trailingZeroBitCount)
  }
}

汎用の slow path

それ以外の基数に対しては、オーバーフローに注意しつつ base を掛け続けて self に到達できるかを調べる素直な実装を使います。

extension BinaryInteger {
  @usableFromInline internal func _slowIsPower(of base: Self) -> Bool {
    // self が 1 なら任意の基数の 0 乗として true
    if self == 1 { return true }

    // base が 0, 1, -1 のときは self == base かどうかで決まる
    if base.magnitude <= 1 { return self == base }

    // |base| >= 2。self を base で割り切れなければ false
    let (bound, remainder) = self.quotientAndRemainder(dividingBy: base)
    guard remainder == 0 else { return false }

    // base を掛け続けて bound に一致するかを確認
    var x: Self = 1
    while x.magnitude < bound.magnitude { x *= base }
    return x == bound
  }
}

プロトコル要件ではなく拡張メソッドにする理由

isPower(of:) はプロトコル要件ではなく BinaryInteger への拡張メソッドとして提供されます。要件にするとカスタム型で独自最適化を差し込む余地が生まれますが、広く使われる BinaryInteger の要件を増やすコストの方が大きいと判断され、まずは拡張メソッドの形で導入されます。

Adding isPower(of:) to BinaryInteger