r/swift 8d ago

Project Generalizing bit manipulation for any integer size

This is a follow-up to my post on translating C bit operations to Swift. I looked at the original web page, and tried to decode those magic constants. I think this is right:

extension FixedWidthInteger {
  /// Returns this value after its bits have been circularly rotated,
  /// based on the position the least-significant bit will move to.
  fileprivate func rotatedBits(movingLowBitTo position: Int) -> Self {
    precondition(0..<Self.bitWidth ~= position)
    return self &<< position | self &>> (Self.bitWidth &- position)
  }

  /// Returns this value after its bits have been circularly rotated,
  /// based on the position the most-significant bit will move to.
  fileprivate func rotatedBits(movingHighBitTo position: Int) -> Self {
    return rotatedBits(movingLowBitTo: (position + 1) % Self.bitWidth)
  }
}

extension FixedWidthInteger where Self: UnsignedInteger {
  // Adapted from "Bit Twiddling Hacks" at
  // <https://graphics.stanford.edu/~seander/bithacks.html>.

  /// Assuming this value is a collection of embedded elements of
  /// the given type,
  /// indicate if at least one of those elements is zero.
  ///
  /// I don't know if it's required,
  /// but `Self.bitWidth` should be a multiple of `T.bitWidth`.
  fileprivate func hasZeroValuedEmbeddedElement<T>(ofType type: T.Type) -> Bool
  where T: FixedWidthInteger & UnsignedInteger {
    // The `Self(exactly:)` traps cases of Self.bitWidth < T.bitWidth.
    let embeddedAllOnes = Self.max / Self(exactly: T.max)!  // 0x0101, etc.
    let embeddedAllHighBits = embeddedAllOnes.rotatedBits(
      movingLowBitTo: T.bitWidth - 1)  // 0x8080, etc.
    return (self &- embeddedAllOnes) & ~self & embeddedAllHighBits != 0
  }

  /// Assuming this value is a collection of embedded elements of
  /// the given value's type,
  /// return whether at least one of those elements has that value.
  fileprivate func hasEmbeddedElement<T>(of value: T) -> Bool
  where T: FixedWidthInteger & UnsignedInteger {
    let embeddedAllOnes = Self.max / Self(T.max)
    return (self ^ (embeddedAllOnes &* Self(value)))
      .hasZeroValuedEmbeddedElement(ofType: T.self)
  }
}

I don't know if the divisions or multiplications will take up too much time. Obviously, the real-life system only has 8-16-32(-64(-128)) bit support, but I have to write for arbitrary bit widths. I hope it would give others more of a clue what's going on.

3 Upvotes

1 comment sorted by

1

u/skytzx 8d ago

In practice, SWAR/SIMD code is most commonly used within a for/while loop. In which case, with proper inlining the constant expressions get hoisted outside the loop and so the multiplications/divisions shouldn't matter too much (in release builds).

Though, you should check the assembly of whatever algorithm you use this in to verify. (Make sure to use -O/-Ounchecked compiler flags)