首页 > 代码库 > 位操作(求[a, b] 中二进制位为1的个数最多的数)

位操作(求[a, b] 中二进制位为1的个数最多的数)

传送门

题意:求区间[a, b]中二进制位为1的个数最多的那个数,如果存在多解,则输出最小的那个。(0 <= a <= b)

 

关键: 对一个数a可以利用 a | (a + 1) 来将a的二进制位中最低的0设置为1

附上代码:

 

 1 #include <stdio.h> 2  3 typedef long long ll; 4  5 int main(void) { 6     int n; 7     scanf("%d", &n); 8     while (n-- > 0) { 9         ll l, r;10         scanf("%lld %lld", &l, &r);11 12         ll res = l;13         while ((res|(res+1)) <= r) {14             res |= res + 1; // set the lowest 015         }16         printf("%lld\n", res);17     }18 19     return 0;20 }

 

位操作(求[a, b] 中二进制位为1的个数最多的数)