设置n个最高位的位操作

Question

我有以下函数，用于设置N个最高位，例如 set_n_high(8) == 0xff00000000000000

uint64_t set_n_high(int n)
{
    uint64_t v = 0;
    int i;
    for (i = 63 ; i > 63 - n; i--) {
        v |= (1llu << i);
    }

    return v;
}

现在出于好奇，有没有不使用循环（或查找表）的方法在C语言中实现相同的操作？

编辑：n = 0和n = 64是需要处理的情况，就像循环变量一样。

- user964970

---

如果 n = 0 或 n = 64 不起作用，你是否可以接受？这将允许一些简化。 - harold

@harold 抱歉，我完全误解了。 n = 64 和 n = 0 也必须可行。不过，n < 0 和 n > 64 不是问题所在。 - user964970

哦，那我恐怕我的回答会毫无用处。 - harold

有点吹毛求疵的想法：前两个发布的答案使用了0uLL。由于这是uint64_t，因此可以使用((uint64_t)0)，因为unsigned long long可能比uint64_t更宽，所以不必要去那么大的尺寸。 - chux - Reinstate Monica

@harold并不完全正确，因为还可以添加一些边缘情况的简单检查。chux，请使用UINT64_C(0)。 - user964970

@user964970 退休的变更应该在帖子中反映出来（使用“[编辑]”）。 - chux - Reinstate Monica

Answer 1

如果不考虑情况 n = 0 的情况，您可以将其简化为以下代码：

uint64_t set_n_high(int n)
{
    return ~UINT64_C(0) << (64 - n);
}

如果你可以接受“奇怪的转换次数”（未定义行为，但适用于我的计算机），那么你甚至可以简化它：

uint64_t set_n_high(int n)
{
    return ~UINT64_C(0) << -n;
}

如果你可以容忍 n = 64 的情况不能工作，那么你可以简化它为

uint64_t set_n_high(int n)
{
    return ~(~UINT64_C(0) >> n);
}

如果使用这种方式需要验证n，那么速度不会更快。否则，可能会更快。

如果你不满意两种情况都无法解决的话，问题就有些棘手了。这里提供一个建议（可能有更好的方法）：

uint64_t set_n_high(int n)
{
    return ~(~UINT64_C(0) >> (n & 63)) | -(uint64_t)(n >> 6);
}

请注意，取一个无符号数的相反数是完全被定义的。

- harold

---

我唯一不想发生的事情就是我的电脑爆炸。 - Fiddling Bits

@GradyPlayer 不是很确定，尤其是在我编辑之前的那个版本。它会移动64位，这是未定义行为 - 实际上通常相当于移动0位，这也不起作用。在PPC上可能有效。 - harold

Answer 2

uint64_t set_n_high(int n) {
    return ((1llu << n) - 1) << (64-n);
}

- jwodder

---

请注意，这不是原始代码的替代品。当n = 0和n = 64时，请小心出现的问题。 - nos

Answer 3

参考@harold的答案，稍作修改：

 uint64_t set_n_high(int n)
{
int carry = n>>6;
return ~((~0uLL >> (n-carry)) >> carry);
}

- Grady Player

---

我可以建议使用 carry = n & 1 吗？ - harold

@Harold，进位的目的是如果n==64，则为True...我认为这是最好的...但我不确定。 - Grady Player

哦，这和以前有点不同。那么 carry = n >> 6 怎么样？那个 & 真的是多余的。 - harold

@harold 我不希望n-carry的值低于零...但我想你可能是对的。只是想表达得更明确。 - Grady Player

Answer 4

使用条件语句处理n == 0，然后问题就变得非常简单。

uint64_t set_n_high(int n) {
/*  optional error checking:
    if (n < 0 || n > 64) do something */
    if (n == 0) return 0;
    return -(uint64_t)1 << 64 - n;
}

实际上，没有比这更复杂的原因。从int到uint64_t的强制转换已经完全规定好了，否定和移位也是（因为如果n在[0,64]范围内，移位量保证在[0,63]之间）。

- Stephen Canon

---

只有为了可爱或者混淆视听，才需要做比你已经拥有的更加复杂的事情。 - Fiddling Bits

Answer 5

就其价值而言，到目前为止（处理0-64个n的帖子中），这篇帖子在x86_64和树莓派上产生了最少的汇编代码（并执行了1个分支操作）（使用gcc 4.8.2）。它看起来相当可读。

uint64_t set_n_high2(int n) 
{
    uint64_t v = 0;

    if (n != 0) {
        v = ~UINT64_C(0) << (64 - n);
    }

    return v;
}

- nos

Answer 6

嗯，我正在展示一个看起来很奇怪的东西。
:)

/* works for 0<=n<=64 */
uint64_t set_n_high(int n)
{
    return ~0llu << ((64 - n) / 4) << ((64 - n) * 3 / 4);
}

- starrify

---

@harold 嗯，是的，我的意图就是让它变得奇怪.. XD 基本思路是将移位量分成两部分，以避免未定义行为<<64的问题。 :) - starrify

问题的目的不是产生奇怪的答案，而是产生高效的答案。 - Vitruvie

@Saposhiente 同意。实际上，你也可以提醒我“SO不想要奇怪的答案，而是正确的答案”。但请问自己，在相信它效率低下之前，你是否曾经计时过它，看过编译器为其生成的汇编代码，或者直接使用大脑将其翻译成汇编语言？在发布答案之前，我已经完成了所有这些步骤，请告诉我是否发现任何结果表明我的答案与其他答案相比显然低效。 - starrify