C++ 中文周刊 2025-01-12 第175期

王很水

发布于 2025-02-04 15:38:19

7400

代码可运行

文章被收录于专栏：C++ 动态新闻推送C++ 动态新闻推送

运行总次数：0

代码可运行

文章

Counting the digits of 64-bit integers

其实比较常规，就是查表

int int_log2(uint64_t x) { return63 - __builtin_clzll(x | 1); } // c++20可以用bit_width
int digit_count(uint64_t x) {
staticuint64_t table[] = {9,
                             99,
                             999,
                             9999,
                             99999,
                             999999,
                             9999999,
                             99999999,
                             999999999,
                             9999999999,
                             99999999999,
                             999999999999,
                             9999999999999,
                             99999999999999,
                             999999999999999ULL,
                             9999999999999999ULL,
                             99999999999999999ULL,
                             999999999999999999ULL,
                             9999999999999999999ULL};
int y = (19 * int_log2(x) >> 6);
  y += x > table[y];
return y + 1;
}

或者更极端一点

int alternative_digit_count(uint64_t x) {
staticuint64_t table[64][2] = {
    { 0x01, 0xfffffffffffffff6ULL },
    { 0x01, 0xfffffffffffffff6ULL },
    { 0x01, 0xfffffffffffffff6ULL },
    { 0x01, 0xfffffffffffffff6ULL },
    { 0x02, 0xffffffffffffff9cULL },
    { 0x02, 0xffffffffffffff9cULL },
    { 0x02, 0xffffffffffffff9cULL },
    { 0x03, 0xfffffffffffffc18ULL },
    { 0x03, 0xfffffffffffffc18ULL },
    { 0x03, 0xfffffffffffffc18ULL },
    { 0x04, 0xffffffffffffd8f0ULL },
    { 0x04, 0xffffffffffffd8f0ULL },
    { 0x04, 0xffffffffffffd8f0ULL },
    { 0x04, 0xffffffffffffd8f0ULL },
    { 0x05, 0xfffffffffffe7960ULL },
    { 0x05, 0xfffffffffffe7960ULL },
    { 0x05, 0xfffffffffffe7960ULL },
    { 0x06, 0xfffffffffff0bdc0ULL },
    { 0x06, 0xfffffffffff0bdc0ULL },
    { 0x06, 0xfffffffffff0bdc0ULL },
    { 0x07, 0xffffffffff676980ULL },
    { 0x07, 0xffffffffff676980ULL },
    { 0x07, 0xffffffffff676980ULL },
    { 0x07, 0xffffffffff676980ULL },
    { 0x08, 0xfffffffffa0a1f00ULL },
    { 0x08, 0xfffffffffa0a1f00ULL },
    { 0x08, 0xfffffffffa0a1f00ULL },
    { 0x09, 0xffffffffc4653600ULL },
    { 0x09, 0xffffffffc4653600ULL },
    { 0x09, 0xffffffffc4653600ULL },
    { 0x0a, 0xfffffffdabf41c00ULL },
    { 0x0a, 0xfffffffdabf41c00ULL },
    { 0x0a, 0xfffffffdabf41c00ULL },
    { 0x0a, 0xfffffffdabf41c00ULL },
    { 0x0b, 0xffffffe8b7891800ULL },
    { 0x0b, 0xffffffe8b7891800ULL },
    { 0x0b, 0xffffffe8b7891800ULL },
    { 0x0c, 0xffffff172b5af000ULL },
    { 0x0c, 0xffffff172b5af000ULL },
    { 0x0c, 0xffffff172b5af000ULL },
    { 0x0d, 0xfffff6e7b18d6000ULL },
    { 0x0d, 0xfffff6e7b18d6000ULL },
    { 0x0d, 0xfffff6e7b18d6000ULL },
    { 0x0d, 0xfffff6e7b18d6000ULL },
    { 0x0e, 0xffffa50cef85c000ULL },
    { 0x0e, 0xffffa50cef85c000ULL },
    { 0x0e, 0xffffa50cef85c000ULL },
    { 0x0f, 0xfffc72815b398000ULL },
    { 0x0f, 0xfffc72815b398000ULL },
    { 0x0f, 0xfffc72815b398000ULL },
    { 0x10, 0xffdc790d903f0000ULL },
    { 0x10, 0xffdc790d903f0000ULL },
    { 0x10, 0xffdc790d903f0000ULL },
    { 0x10, 0xffdc790d903f0000ULL },
    { 0x11, 0xfe9cba87a2760000ULL },
    { 0x11, 0xfe9cba87a2760000ULL },
    { 0x11, 0xfe9cba87a2760000ULL },
    { 0x12, 0xf21f494c589c0000ULL },
    { 0x12, 0xf21f494c589c0000ULL },
    { 0x12, 0xf21f494c589c0000ULL },
    { 0x13, 0x7538dcfb76180000ULL },
    { 0x13, 0x7538dcfb76180000ULL },
    { 0x13, 0x7538dcfb76180000ULL },
    { 0x13, 0x7538dcfb76180000ULL },
};
intlog = int_log2(x);
uint64_t low = table[log][1];
uint64_t high = table[log][0];
return (x + low < x ) + high;
}

评论区大哥给了一个更快的

inline uint8_t digitCounts64[]{ 19, 19, 19, 19, 18, 18, 18, 17, 17, 17, 16, 16, 16, 16, 15, 15, 15, 14, 14, 14, 13, 13, 13, 13, 12, 12, 12, 11, 11, 11, 10, 10, 10,
10, 9, 9, 9, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1 };

inlineuint64_t digitCountThresholds64[]{ 0ull, 9ull, 99ull, 999ull, 9999ull, 99999ull, 999999ull, 9999999ull, 99999999ull, 999999999ull, 9999999999ull,
99999999999ull, 999999999999ull, 9999999999999ull, 99999999999999ull, 999999999999999ull, 9999999999999999ull, 99999999999999999ull, 999999999999999999ull,
9999999999999999999ull };

inline uint64_t fastDigitCount(const uint64_t inputValue) {
constuint64_t originalDigitCount{ digitCounts64[__builtin_clzll(inputValue)] };
return originalDigitCount + (inputValue > digitCountThresholds64[originalDigitCount]);
}

另外这个大哥写了个json库很快。和glaze有一拼 https://github.com/RealTimeChris/Jsonifier/

C++26: a placeholder with no name

总算不用使用 decltype(std::ignore) _;了 c++26支持了

Inside STL: Waiting for a std::atomic std::shared_ptr T to change part 1

Part2

省流std::atomic<std::shared_ptr>::notify_one linux平台由于futex的问题，没有很好的实现

windows有waitonaddress

constexpr std::string的一个好处

可以写编译期测试 static_assert

constexpr std::string
decode(std::span<const unsigned char> payload)
{
staticconstexprunsignedchar MASK{0x7F};
std::string                    result{};

int           shift{};
unsignedchar mask{MASK};
for(unsignedchar scratch{}; auto c : payload) {
    constunsignedchar realChar =
      ((c & mask) << shift) | scratch;
    scratch = (c & (~mask)) >> (7 - shift);

    ++shift;
    mask >>= 1;

    result += static_cast<char>(realChar);

    if(7 == shift) {
      result += static_cast<char>(scratch);
      shift   = 0;
      mask    = MASK;
      scratch = 0;
    }
  }

return result;
}

constexpr auto make_array(auto... values)
{
returnstd::array<unsignedchar, sizeof...(values)>{
    static_cast<unsignedchar>(values)...};
}

void Use()
{
constexprauto payload{make_array(0xd3,
                                    0x74,
                                    0x1b,
                                    0xce,
                                    0x2e,
                                    0x83,
                                    0xa6,
                                    0xcd,
                                    0x29,
                                    0x88,
                                    0x5e,
                                    0xc6,
                                    0xd3,
                                    0x5d)};
constexprauto payload2{make_array(0xc8,
                                     0x32,
                                     0x9b,
                                     0xfd,
                                     0x66,
                                     0x81,
                                     0x86,
                                     0xab,
                                     0x55,
                                     0x08,
                                     0x44,
                                     0x45,
                                     0xa7,
                                     0xe7,
                                     0xa0,
                                     0xf4,
                                     0x1c,
                                     0x34,
                                     0x46,
                                     0x97,
                                     0xc7,
                                     0xeb,
                                     0xb4,
                                     0xfb,
                                     0x0c,
                                     0x0a,
                                     0x83,
                                     0xe6,
                                     0x74,
                                     0xb2,
                                     0x4e,
                                     0x37,
                                     0xa7,
                                     0xcb,
                                     0xd3,
                                     0xee,
                                     0x33,
                                     0x28,
                                     0x4c,
                                     0x07,
                                     0x8d,
                                     0xdf,
                                     0x6d,
                                     0x78,
                                     0x9a,
                                     0x5d,
                                     0x06,
                                     0xd1,
                                     0xd3,
                                     0xed,
                                     0x72,
                                     0x08,
                                     0xe4,
                                     0x4c,
                                     0x8f,
                                     0xcb,
                                     0x2c,
                                     0x50,
                                     0x7a,
                                     0xee,
                                     0x3e,
                                     0xd1,
                                     0x41,
                                     0x69,
                                     0xfa,
                                     0x0f)};

auto smsText = decode(payload);
std::println("{}", smsText);

auto smsText2 = decode(payload2);
std::println("{}", smsText2);

static_assert("Simple SMS text." == decode(payload));
static_assert(
    "Hello, C++! This is checking a std::string at "
    "compile time! Nice, isn't it?" ==
    decode(payload2));
}