c - 基数排序中的位函数

Question

基数排序是排序键，作为以 M 数为基数表示的数字。为了使用基数排序，我需要了解bits函数。

unsigned bits(int x, int k, int j)
{ return (x >> k) & ~(~0 << j); }

根据我读到的文件，上面说

It computes the j bits which appear k bits from the right of x.

但它太短了，并且有一些我几乎无法理解的符号(即 >> 、 ~ 和 & )。我尝试对此进行测试，它仅返回两个值 0 和 1。我真的需要对此及其真正功能的解释

Answer 1

在函数 unsigned bits(int x, int k, int j) 中, x是要排序的值，k是从 x 中提取的位的最右边位置，和j是从 x 中提取的位数。

如果你想用 4 位值进行基数排序，你可以设置 j至 4 和 k为值 0，然后为 4，然后为 8，依此类推。

该函数的工作原理如下。首先，它发生变化x通过k右边的位。这是通过表达式 (x >> k) 完成的。 。

另一个表达式是(~0 << j) 。 ~0反转值 0 的所有位。这会产生一个所有位都为 1 的值。然后该值左移 j位。然后您会得到一个所有位都为 1 的值，以及 j最右边的位为 0。

由于 (~0 << j) 前面的 ~ 运算符，该值的所有位再次反转。 。然后，您将获得一个所有位都设置为 0 的值，并且 j最右边的位设置为 1。

然后将该值与第一个表达式 x >> k 的结果进行 and 运算组合。 。通过“与”运算，所有为零的位都被强制为零。由于第二个表达式的所有位都为 0，除了 j 之外。不太重要。结果是所有位都强制为 0，除了 j 之外。不太重要(最右边)。

最终结果是返回j偏移量 k 处的位在值x中。

例如，如果 x 的位是 100101001 和 k是 3 并且 j 是 3，结果将为 0000000101。

这相当于从数字中提取数字的二进制。