C/C++ 位运算

得到一个二进制数的最高有效位

等价问题

获取比一个数小的最大2的次幂
exp(int(log2(x)), 2)
Calculates the smallest integral power of two that is not smaller than x.

可能方法

把自然数均匀map到0~1（单向就行
写个 naive approach 然后交给 compiler
查表
bitset 一直把 lowbit 去除
__builtin_clz

GCC有内建函数__builtin_clz（clz表示Count Leading Zeros，统计前导零个数），可以直接使用：

unsigned msb(unsigned x)
{
    return 31 - __builtin_clz(x);
}

当然，unsigned类型的大小依赖于平台，并不一定占32个bit，所以更好的写法是：

#include <limits.h>
unsigned msb(unsigned x)
{
    return sizeof(unsigned) * CHAR_BIT - 1 - __builtin_clz(x);
}

__builtin_clz 当参数为0时结果未定义，所以上面这个函数在参数为0时结果也未定义，使用时需要特判。不过，如果希望msb(0)的结果为0，可以简单地用x|1代替原来的x，不会影响其他结果。

除了__builtin_clz外，还有__builtin_clzl和__builtin_clzll，分别对应参数为unsigned long和unsigned long long的情形。

关于速度，将上面的代码使用x86-64 gcc 10.2编译，开-O2后生成代码如下：

msb:
        bsr     edi, edi
        mov     eax, 31
        xor     edi, 31
        sub     eax, edi
        ret

可以发现原理主要是使用了bsr（Bit Scan Reverse，逆向位扫描）这个指令，这是Intel 80386后引入的指令，它的作用是 [1](https://www.zhihu.com/question/35361094/answer/1648676503#ref_1)：

Scans source operand for first bit set. Sets ZF if a bit is found set and loads the destination with an index to first set bit. Clears ZF is no bits are found set. BSF scans forward across bit pattern (0-n) while BSR scans in reverse (n-0).

即从高位到低位扫描源操作数的二进制位，如果没有找到1，则将标志位ZF设为0；如果找到了，则把标志位ZF设为1，且将第一个1所在的位序号传入目的操作数。另一个指令bsf（Bit Scan Forward，前向位扫描）与它类似，只不过方向是从低位到高位。

这个方法可以认为是O(1)的，而且效率比log2 高很多。

其实C++中可以直接用std::__lg来实现前面提到的功能，编译出来也是一样的：

#include <bitset>
#include <climits>
#include <iostream>

using namespace std;

unsigned msb(unsigned x) {
    return sizeof(unsigned) * CHAR_BIT - 1 - __builtin_clz(x);
}

auto main(int argc, char const *argv[]) -> int {
    int x;
    cin >> x;
    cout << (1 << msb(x)) << endl;
    return EXIT_SUCCESS;
}

std::bit_ceil

#include <bit>
#include <bitset>
#include <iostream>
 
auto main() -> signed int // :()
{
    using bin = std::bitset<8>;
 
    for (unsigned x{0}; x != 10; ++x)
    {
        unsigned const z = std::bit_ceil(x); // `ceil2` before P1956R1
 
        std::cout << "bit_ceil( " << bin(x) << " ) = " << bin(z) << '\n';
    }
}

Output:

bit_ceil( 00000000 ) = 00000001
bit_ceil( 00000001 ) = 00000001
bit_ceil( 00000010 ) = 00000010
bit_ceil( 00000011 ) = 00000100
bit_ceil( 00000100 ) = 00000100
bit_ceil( 00000101 ) = 00001000
bit_ceil( 00000110 ) = 00001000
bit_ceil( 00000111 ) = 00001000
bit_ceil( 00001000 ) = 00001000
bit_ceil( 00001001 ) = 00010000

https://en.cppreference.com/w/cpp/numeric/bit_ceil

单/双浮点数取绝对值

IEEE-754

https://googles.plus/2021/11/13/ieee-754-xue-xi-bi-ji/

根据 IEEE-754 标准，sign-bit（符号位）决定了一个浮点数的正负，这里我们使用几种方式进行掩码取绝对值。

#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>

constexpr uint64_t mask = 0x7fffffffffffffff;
constexpr double   d1   = -3.1415926;

void print(double (&func)(double), double x) {
    // std::cout << "-----------------------" << std::endl;
    std::cout << std::fixed << std::setprecision(8) << func(x) << std::endl;
    std::cout << "-----------------------" << std::endl;
}

double c_dynamic_cast(double x) {
    return (double) (((uint64_t) x) & mask);
}

double cpp_static_cast(double x) {
    return static_cast<double>(static_cast<uint64_t>(x) & mask);
}

double ptr_cast_fabs(double x) {
    return *(double *) (*(uint64_t *) (&x) &= mask, &x);
}

double reinterprete_cast_fabs(double x) {
    return *reinterpret_cast<double *>(*reinterpret_cast<uint64_t *>(&x) &= mask, &x);
}

double type_pun_fabs(double x) {
    union {
        uint64_t i;
        double   d;
    } u;
    u.d = x;
    u.i &= mask;
    return u.d;
}

auto main() -> int {
    std::cout << std::hex << "0x" << *(uint64_t *) (&d1) << '\n';
    std::cout << "Failed Situation: data loss and complement format dislay" << '\n';
    std::cout << "c_dynamic_cast:" << '\n';
    print(c_dynamic_cast, d1);
    std::cout << "cpp_static_cast:" << '\n';
    print(cpp_static_cast, d1);
    std::cout << "Succedded Situation:" << '\n';
    std::cout << "reinterprete_cast:" << '\n';
    print(reinterprete_cast_fabs, d1);
    std::cout << "ptr_cast_fabs:" << '\n';
    print(ptr_cast_fabs, d1);
    std::cout << "type_pun_fabs:" << '\n';
    print(type_pun_fabs, d1);
    std::cout << "fabs:" << '\n';
    print(fabs, d1);
    return EXIT_SUCCESS;
}

结果：

0xc00921fb4d12d84a
Failed Situation: data loss and complement format dislay
c_dynamic_cast:
9223372036854775808.00000000
-----------------------
cpp_static_cast:
9223372036854775808.00000000
-----------------------
Succedded Situation:
reinterprete_cast:
3.14159260
-----------------------
ptr_cast_fabs:
3.14159260
-----------------------
type_pun_fabs:
3.14159260
-----------------------
fabs:
3.14159260

从结果看来，前两种由于会精度丢失，所以是错误的。至于数值，则是由先取整后以补码形式输出造成的，读者可以自己验证。

后几种方法对变量所在内存做“重新解读”，所以没有触发变量本身的类型转换，所以结果依然正确。

一些C/C++位运算优化