算法与计算机科学graphics.stanford.edu编辑精选
位运算技巧集
Bit Twiddling Hacks
2011 — 2024，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。多年来它一直是程序员查阅底层位级优化和算法思路的参考。
为什么经久不衰：这些技巧跨越编译器和硬件演进仍有教育价值：既能帮助理解底层算法，也能在性能敏感场景中启发优化思路。
HN 评论精选
位运算技巧在实际高性能运行时中有直接应用。
这类技巧是让我们把 Scala.js 的 64 位整数做快的重要组成部分（据称是 JavaScript 上已知最快的 64 位整数实现）。实现见[1]，详细解释、基准和其他技巧见[2] 4.4 节。
sjrd查看英文原文
This kind of hacks is a major part of how we made Scala.js' 64-bit integers fast (the fastest known implementation of 64-bit integers on JavaScript). See [1] for the implementation, and [2] at section 4.4 for the long explanation with benchmarks and the other tricks we use. [1] https://github.com/scala-js/scala-js/blob/v1.3.1/linker-private-library/src/main/scala/org/scalajs/linker/runtime/RuntimeLong.scala [2] https://lampwww.epfl.ch/~doeraene/thesis/doeraene-thesis-2018-cross-platform-language-design.pdf
编译器与硬件优化会吸收手工位运算技巧。
我最喜欢这些技巧的一点是它们会兜一圈回来：程序员想出绕来绕去的方法在某个原始操作上骗过编译器，然后 CPU 厂商为这些操作加入专用指令，最终编译器又骗过程序员——把它自作聪明的方法删掉，改发一条指令。
jsheard查看英文原文
My favorite thing about these is how they come full circle - programmers find convoluted ways to outsmart the compiler in some primitive operation, but then CPU manufacturers add dedicated instructions for those operations, and eventually the compilers outsmart the programmer by deleting their smartass method and emitting a single instruction instead https://godbolt.org/z/nPdrcz
这类知识在面试和实际工作中都可能有用，不应一概否定。
上次求职面试，我得实现 popcount 并解释如何优化。我写出了朴素实现和查表优化，只模糊记得 Bit Twiddling 的处理方法，在面试官提示下实现并解释了 O(set bits) 的“Brian Kernighan 法”。我拿到了这份工作。现在嘲笑这类代码面试不现实、没帮助很时髦，但入职第一周碰巧就用到了这个函数。显然已有高效实现包括 intrinsics，但知道如何推导高效实现肯定无害。我的职责后来变了，底层算法知识仍重要。我不确定把它放进面试总体是否好主意，设计好面试当然是大话题，但在我这个例子里，它恰好是对我能力相关且公平的测试。
klmr查看英文原文
At my last job interview I had to implement popcount and explain how to optimise it (amongst other things). I was able to jot down a naïve implementation and the obvious optimisation based on a lookup tables. I only vaguely remembered the Bit Twiddling treatment of the subject but, with a bit of nudging from the interviewer, I managed to implement and explain the variant that runs in O(set bits) (“Brian Kernighan's way”). I got the job. Now, it’s fashionable to deride this this kind of code interview as unrealistic and unhelpful. But in my first week on the job, by sheer coincidence, I had to use the function. Obviously there are existing, efficient implementations, including intrinsics. But knowing how to derive an efficient implementation certainly didn’t harm. My job has since evolved into different responsibilities but low-level algorithmic knowledge is still important. I’m not sure testing for it in job interviews is generally a good idea, and designing good job interviews is certainly a big topic. But in my particular case it happened to be a relevant, fair test of my abilities.
现代 GPU/图形编程仍用位技巧，但硬件已提供 popcount、ctz 等指令。
我喜欢这类东西，并在 GPU 编程等地方使用。情况已多方面变化：popcount 和 count-trailing-zeros 现在通常是快速指令；乘法也和别的操作一样快，不再需要避免。举两个例子：[1] 计算贝塞尔路径连续四段所用字节数的总和——每段可以是 lineto/quadto/curveto，可以是路径结尾与否，且是 i16 或 f32。4 个 tag 字节打包进一个 32 位字，算出这些再求和。[2] 把递归细分线性化为迭代循环。栈深度用字中零的个数表示，所以压栈是左移，弹栈是右移。结果你会想一次弹多层，层数用 countTrailingZeros 计算。([2] 是实验性 Rust 代码，但我会把它改写成 compute shader)
raphlinus查看英文原文
I love these kinds of things and use them in GPU programming, among other things. Things have changed in a variety of ways: population count and count-trailing-zeros are generally available as fast instructions now. Multiply is also now just as fast as other operations, so is not to be avoided. A couple examples. [1] computes the sum of the number of bytes used of four consecutive segments of a bezier path - each segment can be lineto, quadto, or curveto, can be the end of a path or not, and be i16 or f32. 4 tag bytes are packed into a 32 bit word, it computes all these, then sums them together. [2] linearizes a recursive subdivision into an iterative loop. The stack depth is represented as the number of zeros in a word, so pushing the stack is a left shift, and popping is a right shift. It turns out you want to pop multiple levels at once, and the number of levels is computed by countTrailingZeros. ([2] is experimental Rust code, but I will adapt this into a compute shader) [1]: https://github.com/linebender/piet-gpu/blob/main/piet-wgsl/shader/shared/pathtag.wgsl#L48 [2]: https://github.com/linebender/kurbo/blob/euler/src/euler.rs#L630
历次讨论
同类还值得读
如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选游戏中的六边形网格
Hexagonal grids for games
Red Blob Games 的六边形网格教程，系统讲解游戏中六边形网格的坐标系（轴向、立方坐标等）、邻居计算、与像素坐标互转、视野与寻路等常见问题。
算法与计算机科学上首页 5 次 · 2013–2020redblobgames.com编辑精选