The Curious Engineer

All blogs / Performance / optimization

Bits, Math and Performance(?)

bitmath.blogspot.com

50% bits, 50% math (allegedly)

Performance / optimizationAlgorithms / data structuresMathCPU / microarchitectureAssembly

’15’20’25
Posts
50 from 12 Sep 2012 to 28 Jul 2026
Posting
now and then (4 in the last year)
Kind
personal blog
Feed
https://bitmath.blogspot.com/feeds/posts/default

2026 3

  1. Asking a bit-permutation what it does (and cloning it)
  2. Fenwick trees for products mod 2ⁿ
  3. What is abs(x - y)

2025 2

  1. Computing 264 mod N, where N is a u64
  2. From Boolean logic to bitmath and SIMD: transitive closure of tiny graphs

2024 10

  1. Bit-permuting 16 u32s at once with AVX-512
  2. Histogramming bytes with positional popcount (GF2P8AFFINEQB edition)
  3. Enumerating identities, part 2
  4. Sorting the nibbles of a u64
  5. Sharpening a lower bound with KnownBits information
  6. Multiplying 64x64 bit-matrices with GF2P8AFFINEQB
  7. Implementing grevmul with GF2P8AFFINEQB
  8. Enumerating all mathematical identities (in fixed-size bitvector arithmetic with a restricted set of operations) of a certain size
  9. The solutions to 𝚙𝚘𝚙𝚌𝚗𝚝(𝚡) < 𝚝𝚣𝚌𝚗𝚝(𝚡) and why there are Fibonacci[n] of them below 2ⁿ
  10. Partial sums of popcount

2023 7

  1. Permuting bits with GF2P8AFFINEQB
  2. Propagating bounds through bitwise operations
  3. Some ways to check whether an unsigned sum wraps
  4. grevmul
  5. Transposing a 16x16 bitmatrix
  6. Column-oriented row reduction
  7. Weighted popcnt

2022 1

  1. Bit-level commutativity and "sum gap" revisited

2021 2

  1. Integer promotion does not help performance
  2. Partial sums of blsi and blsmsk

2020 2

  1. The range a sum cannot fall within
  2. Information on incrementation

2019 1

  1. Square root of bitwise NOT

2018 2

  1. Signed wrapping is meaningful and algebraically nice
  2. Implementing Euclidean division

2017 3

  1. Notes on negation
  2. Bit-level commutativity
  3. Visualizing addition, subtraction and bitwise complement

2016 1

  1. Parallel prefix/suffix operations

2014 1

  1. A bitwise relational domain

2013 4

  1. Determining the cardinality of a set described by a mask and bounds
  2. Announcing haroldbot
  3. Carryless multiplicative inverse
  4. Improving bounds when some bits have a known value

2012 11

  1. Tesseral arithmetic - useful snippets
  2. Tesseral arithmetic
  3. The basics of working with the signbit
  4. Calculating the lower and upper bound of the bitwise OR of two variables that are bounded and may have bits known to be zero
  5. Calculating the lower and upper bounds of the bitwise AND of two bounded variables
  6. Calculating the upper bound of the bitwise OR of two bounded variables
  7. Calculating the lower bound of the bitwise OR of two bounded variables
  8. Divisibility and modular multiplication, even divisors
  9. The basics of working with the rightmost bit
  10. Divisibility and modular multiplication
  11. Divisibility and digital roots