如何在C中获得最右边设置位的位置
How to get position of right most set bit in C
int a = 12;
例如：12 的二进制是 1100，所以答案应该是 3，因为右起第 3 位已设置。
我想要 a 的最后一个设置位的位置。谁能告诉我该怎么做。
注意 ：我只想要位置，这里我不想设置或重置该位。所以它不是关于 Whosebug 的任何问题的重复。
检查 a & 1 是否为 0。如果是，则右移一位，直到它不为零。你移位的次数就是从右边移多少位就是设置的最右边的位。
试试这个
int set_bit = n ^ (n&(n-1));
解释：
如 this 回答中所述，n&(n-1) 取消设置最后设置的位。
因此，如果我们取消设置最后一个设置位并将其与数字异或；根据异或运算的性质，最后设置的位将变为 1，其余位将 return 0
您必须检查从索引 0 开始一直向左的所有 32 位。如果你可以按位 - 并且你的 a 在那个位置有一个位并得到一个非零值，这意味着该位已设置。
#include <limits.h>
int last_set_pos(int a) {
for (int i = 0; i < sizeof a * CHAR_BIT; ++i) {
if (a & (0x1 << i)) return i;
}
return -1; // a == 0
}
在典型的系统上 int 将是 32 位，但是执行 sizeof a * CHAR_BIT 将使您在 a 中获得正确的位数，即使它的大小不同
找到最低有效设置位的（基于 0 的）索引等同于计算给定整数有多少个尾随零。根据您的编译器，有内置函数用于此，例如 gcc 和 clang 支持 __builtin_ctz。
对于 MSVC，您需要实现自己的版本，this answer 另一个问题显示了使用 MSVC 内在函数的解决方案。
鉴于您正在寻找基于 1 的索引，您只需将 ctz 的结果加 1 即可实现您想要的结果。
int a = 12;
int least_bit = __builtin_ctz(a) + 1; // least_bit = 3
请注意，如果 a == 0，则此操作未定义。此外，如果您使用 long 和 long long 而不是 int，则应该使用 __builtin_ctzl and __builtin_ctzll。
根据dbush的解决方案，试试这个：
int rightMostSet(int a){
if (!a) return -1; //means there isn't any 1-bit
int i=0;
while(a&1==0){
i++;
a>>1;
}
return i;
}
这里可以用2s补码的属性。
找到数字的 2s 补码的最快方法是获取最右边的设置位并将所有内容翻转到它的左边。
例如：考虑一个 4 位系统
4=0100
4 的 2s 补码 = 1100，无非是 -4
4&(-4)=0100.
请注意，只有一个设置位及其最右边的设置位 4
类似地，我们可以将其概括为 n.
n&(-n) 将仅包含一个设置位，它实际上位于 n 的最右侧设置位位置。
因为 n&(-n) 中只有一个设置位，所以它是 2 的幂。
所以最后我们可以通过以下方式获得位位置：
log2(n&(-n))+1
您可以通过对 n 和 (n&(n-1) )[ 按位异或来找到最右边设置位的位置=11=]
int pos = n ^ (n&(n-1));
return log2(((num-1)^num)+1);
举例说明：12 - 1100
num-1 = 11 = 1011
num^ (num-1) = 12^11 = 7 (111)
num^ (num-1))+1 = 8 (1000)
log2(1000) = 3（答案）。
这个答案 Unset the rightmost set bit 告诉我们如何获取和取消设置最右边的设置位 对于表示为二进制补码的无符号整数或有符号整数。
获取最右边的设置位,
x & -x
// or
x & (~x + 1)
取消设置最右边的设置位,
x &= x - 1
// or
x -= x & -x // rhs is rightmost set bit
为什么有效
x: leading bits 1 all 0
~x: reversed leading bits 0 all 1
~x + 1 or -x: reversed leading bits 1 all 0
x & -x: all 0 1 all 0
例如，让 x = 112，并为简单起见选择 8 位，尽管这个想法对于所有整数大小都是相同的。
// example for get rightmost set bit
x: 01110000
~x: 10001111
-x or ~x + 1: 10010000
x & -x: 00010000
// example for unset rightmost set bit
x: 01110000
x-1: 01101111
x & (x-1): 01100000
x & ~(x-1) 将最低位隔离为 1。
我继承了这个，并注明它来自 HAKMEM（试试看 here）。它适用于有符号和无符号整数、逻辑或算术右移。它也非常有效。
#include <stdio.h>
int rightmost1(int n) {
int pos, temp;
for (pos = 0, temp = ~n & (n - 1); temp > 0; temp >>= 1, ++pos);
return pos;
}
int main()
{
int pos = rightmost1(16);
printf("%d", pos);
}
n的最左边的位可以用公式得到：
n & ~(n-1)
这是有效的，因为当你计算 (n-1) .. 你实际上是在使所有的零直到最右边的位为 1，最右边的位为 0。
然后你取一个 NOT .. 这给你留下了以下内容：
x= ~（原始数字的位数）+（最右边的 1 位）+ 尾随零
现在，如果您执行 (n & x)，您会得到所需的，因为 n 和 x 中唯一为 1 的位是最右边的位。
呸呸呸……:sweat_smile:
http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/
帮助我理解了这一点。
int main(int argc, char **argv)
{
int setbit;
unsigned long d;
unsigned long n1;
unsigned long n = 0xFFF7;
double nlog2 = log(2);
while(n)
{
n1 = (unsigned long)n & (unsigned long)(n -1);
d = n - n1;
n = n1;
setbit = log(d) / nlog2;
printf("Set bit: %d\n", setbit);
}
return 0;
}
结果如下。
Set bit: 0
Set bit: 1
Set bit: 2
Set bit: 4
Set bit: 5
Set bit: 6
Set bit: 7
Set bit: 8
Set bit: 9
Set bit: 10
Set bit: 11
Set bit: 12
Set bit: 13
Set bit: 14
Set bit: 15
Knuth 7.1.3 中有一个巧妙的技巧，您可以乘以一个 "magic" 数字（通过强力搜索找到），将数字的前几位映射到每个数字的唯一值最右边位的位置，然后你可以使用一个小的查找table。这是 32 位值的该技巧的实现，改编自 nlopt library（MIT/expat 许可）。
/* Return position (0, 1, ...) of rightmost (least-significant) one bit in n.
*
* This code uses a 32-bit version of algorithm to find the rightmost
* one bit in Knuth, _The Art of Computer Programming_, volume 4A
* (draft fascicle), section 7.1.3, "Bitwise tricks and
* techniques."
*
* Assumes n has a 1 bit, i.e. n != 0
*
*/
static unsigned rightone32(uint32_t n)
{
const uint32_t a = 0x05f66a47; /* magic number, found by brute force */
static const unsigned decode[32] = { 0, 1, 2, 26, 23, 3, 15, 27, 24, 21, 19, 4, 12, 16, 28, 6, 31, 25, 22, 14, 20, 18, 11, 5, 30, 13, 17, 10, 29, 9, 8, 7 };
n = a * (n & (-n));
return decode[n >> 27];
}
1-减1表格编号：(a-1)
2- 取其 否定 : ~(a-1)
3- 对原数进行'AND'运算：
int last_set_bit = a & ~(a-1)
减法背后的原因是，当你取反时它设置它的最后一位 1，所以当取 'AND' 它给出最后一个设置位。
设 x 为您的整数输入。
按位与 1。
如果它是偶数，即 0, 0&1 returns 你是 0。
如果是奇数即 1, 1&1 returns 你 1.
if ( (x & 1) == 0) )
{
std::cout << "The rightmost bit is 0 ie even \n";
}
else
{
std::cout<< "The rightmost bit is 1 ie odd \n";
}```
好的，所以数字系统只是使用对数和指数。因此，我将深入探讨一种对我来说真正有意义的方法。
我希望您阅读 this，因为我在那里写了我如何将对数解释为。
当你执行x & -x操作时，它给你最右边的值作为1（例如，它可以是0001000或0000010。现在根据我如何解释对数，最右边的这个值设置位，是我以 2 的速率增长后的 final 值。现在我们有兴趣找到这个答案中的位数，因为不管它是什么，如果你从中减去 1，那正是设置位的 bit-count（这里的位计数从 0 开始，数字计数从 1 开始，所以是的）。但是位数正好是time you expanded for + 1（按照我的逻辑）或者只是我在前面提到的公式link。但是现在，因为我们并不真正需要数字，而是需要位计数，我们也不必担心可能可以是真实的位值（如果数字是 65），因为number 总是 2 的倍数（1 除外）。所以如果你只取值 x & -x 的对数，我们得到位 cou新台币！在提到这个之前我确实看到了一个答案，但深入探究它为什么真正有效是我想写下来的东西。
P.S：你也可以计算位数，然后从中减去1得到bit-count。
int a = 12;
例如：12 的二进制是 1100，所以答案应该是 3，因为右起第 3 位已设置。
我想要 a 的最后一个设置位的位置。谁能告诉我该怎么做。
注意 ：我只想要位置，这里我不想设置或重置该位。所以它不是关于 Whosebug 的任何问题的重复。
检查 a & 1 是否为 0。如果是，则右移一位，直到它不为零。你移位的次数就是从右边移多少位就是设置的最右边的位。
试试这个
int set_bit = n ^ (n&(n-1));
解释：
如 this 回答中所述，n&(n-1) 取消设置最后设置的位。
因此，如果我们取消设置最后一个设置位并将其与数字异或；根据异或运算的性质，最后设置的位将变为 1，其余位将 return 0
您必须检查从索引 0 开始一直向左的所有 32 位。如果你可以按位 - 并且你的 a 在那个位置有一个位并得到一个非零值，这意味着该位已设置。
#include <limits.h>
int last_set_pos(int a) {
for (int i = 0; i < sizeof a * CHAR_BIT; ++i) {
if (a & (0x1 << i)) return i;
}
return -1; // a == 0
}
在典型的系统上 int 将是 32 位，但是执行 sizeof a * CHAR_BIT 将使您在 a 中获得正确的位数，即使它的大小不同
找到最低有效设置位的（基于 0 的）索引等同于计算给定整数有多少个尾随零。根据您的编译器，有内置函数用于此，例如 gcc 和 clang 支持 __builtin_ctz。
对于 MSVC，您需要实现自己的版本，this answer 另一个问题显示了使用 MSVC 内在函数的解决方案。
鉴于您正在寻找基于 1 的索引，您只需将 ctz 的结果加 1 即可实现您想要的结果。
int a = 12;
int least_bit = __builtin_ctz(a) + 1; // least_bit = 3
请注意，如果 a == 0，则此操作未定义。此外，如果您使用 long 和 long long 而不是 int，则应该使用 __builtin_ctzl and __builtin_ctzll。
根据dbush的解决方案，试试这个：
int rightMostSet(int a){
if (!a) return -1; //means there isn't any 1-bit
int i=0;
while(a&1==0){
i++;
a>>1;
}
return i;
}
这里可以用2s补码的属性。
找到数字的 2s 补码的最快方法是获取最右边的设置位并将所有内容翻转到它的左边。
例如：考虑一个 4 位系统
4=0100
4 的 2s 补码 = 1100，无非是 -4
4&(-4)=0100.
请注意，只有一个设置位及其最右边的设置位 4
类似地，我们可以将其概括为 n.
n&(-n) 将仅包含一个设置位，它实际上位于 n 的最右侧设置位位置。
因为 n&(-n) 中只有一个设置位，所以它是 2 的幂。
所以最后我们可以通过以下方式获得位位置：
log2(n&(-n))+1
您可以通过对 n 和 (n&(n-1) )[ 按位异或来找到最右边设置位的位置=11=]
int pos = n ^ (n&(n-1));
return log2(((num-1)^num)+1);
举例说明：12 - 1100
num-1 = 11 = 1011
num^ (num-1) = 12^11 = 7 (111)
num^ (num-1))+1 = 8 (1000)
log2(1000) = 3（答案）。
这个答案 Unset the rightmost set bit 告诉我们如何获取和取消设置最右边的设置位 对于表示为二进制补码的无符号整数或有符号整数。
获取最右边的设置位,
x & -x
// or
x & (~x + 1)
取消设置最右边的设置位,
x &= x - 1
// or
x -= x & -x // rhs is rightmost set bit
为什么有效
x: leading bits 1 all 0
~x: reversed leading bits 0 all 1
~x + 1 or -x: reversed leading bits 1 all 0
x & -x: all 0 1 all 0
例如，让 x = 112，并为简单起见选择 8 位，尽管这个想法对于所有整数大小都是相同的。
// example for get rightmost set bit
x: 01110000
~x: 10001111
-x or ~x + 1: 10010000
x & -x: 00010000
// example for unset rightmost set bit
x: 01110000
x-1: 01101111
x & (x-1): 01100000
x & ~(x-1) 将最低位隔离为 1。
我继承了这个，并注明它来自 HAKMEM（试试看 here）。它适用于有符号和无符号整数、逻辑或算术右移。它也非常有效。
#include <stdio.h>
int rightmost1(int n) {
int pos, temp;
for (pos = 0, temp = ~n & (n - 1); temp > 0; temp >>= 1, ++pos);
return pos;
}
int main()
{
int pos = rightmost1(16);
printf("%d", pos);
}
n的最左边的位可以用公式得到： n & ~(n-1)
这是有效的，因为当你计算 (n-1) .. 你实际上是在使所有的零直到最右边的位为 1，最右边的位为 0。 然后你取一个 NOT .. 这给你留下了以下内容： x= ~（原始数字的位数）+（最右边的 1 位）+ 尾随零
现在，如果您执行 (n & x)，您会得到所需的，因为 n 和 x 中唯一为 1 的位是最右边的位。
呸呸呸……:sweat_smile:
http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/ 帮助我理解了这一点。
int main(int argc, char **argv)
{
int setbit;
unsigned long d;
unsigned long n1;
unsigned long n = 0xFFF7;
double nlog2 = log(2);
while(n)
{
n1 = (unsigned long)n & (unsigned long)(n -1);
d = n - n1;
n = n1;
setbit = log(d) / nlog2;
printf("Set bit: %d\n", setbit);
}
return 0;
}
结果如下。
Set bit: 0
Set bit: 1
Set bit: 2
Set bit: 4
Set bit: 5
Set bit: 6
Set bit: 7
Set bit: 8
Set bit: 9
Set bit: 10
Set bit: 11
Set bit: 12
Set bit: 13
Set bit: 14
Set bit: 15
Knuth 7.1.3 中有一个巧妙的技巧，您可以乘以一个 "magic" 数字（通过强力搜索找到），将数字的前几位映射到每个数字的唯一值最右边位的位置，然后你可以使用一个小的查找table。这是 32 位值的该技巧的实现，改编自 nlopt library（MIT/expat 许可）。
/* Return position (0, 1, ...) of rightmost (least-significant) one bit in n.
*
* This code uses a 32-bit version of algorithm to find the rightmost
* one bit in Knuth, _The Art of Computer Programming_, volume 4A
* (draft fascicle), section 7.1.3, "Bitwise tricks and
* techniques."
*
* Assumes n has a 1 bit, i.e. n != 0
*
*/
static unsigned rightone32(uint32_t n)
{
const uint32_t a = 0x05f66a47; /* magic number, found by brute force */
static const unsigned decode[32] = { 0, 1, 2, 26, 23, 3, 15, 27, 24, 21, 19, 4, 12, 16, 28, 6, 31, 25, 22, 14, 20, 18, 11, 5, 30, 13, 17, 10, 29, 9, 8, 7 };
n = a * (n & (-n));
return decode[n >> 27];
}
1-减1表格编号：(a-1)
2- 取其 否定 : ~(a-1)
3- 对原数进行'AND'运算：
int last_set_bit = a & ~(a-1)
减法背后的原因是，当你取反时它设置它的最后一位 1，所以当取 'AND' 它给出最后一个设置位。
设 x 为您的整数输入。 按位与 1。 如果它是偶数，即 0, 0&1 returns 你是 0。 如果是奇数即 1, 1&1 returns 你 1.
if ( (x & 1) == 0) )
{
std::cout << "The rightmost bit is 0 ie even \n";
}
else
{
std::cout<< "The rightmost bit is 1 ie odd \n";
}```
好的，所以数字系统只是使用对数和指数。因此，我将深入探讨一种对我来说真正有意义的方法。
我希望您阅读 this，因为我在那里写了我如何将对数解释为。
当你执行x & -x操作时，它给你最右边的值作为1（例如，它可以是0001000或0000010。现在根据我如何解释对数，最右边的这个值设置位，是我以 2 的速率增长后的 final 值。现在我们有兴趣找到这个答案中的位数，因为不管它是什么，如果你从中减去 1，那正是设置位的 bit-count（这里的位计数从 0 开始，数字计数从 1 开始，所以是的）。但是位数正好是time you expanded for + 1（按照我的逻辑）或者只是我在前面提到的公式link。但是现在，因为我们并不真正需要数字，而是需要位计数，我们也不必担心可能可以是真实的位值（如果数字是 65），因为number 总是 2 的倍数（1 除外）。所以如果你只取值 x & -x 的对数，我们得到位 cou新台币！在提到这个之前我确实看到了一个答案，但深入探究它为什么真正有效是我想写下来的东西。
P.S：你也可以计算位数，然后从中减去1得到bit-count。