找出第K个字符I

//
// Created by yhj on 2025/7/4.
//

#include <iostream>

using namespace std;

class Solution {
    public:
        char kthCharacter(int k) {
// 初始字符串 word = "a"，长度为 1 .
// 每次扩展，先复制一份 word，之后，word中的每个字符 +1 变成新的字符串
// 最后将新字符串添加到旧字符串之后。
// 第 i 次扩展后长度成倍增长，例如:
// 第 0 次字符串长度为 2 的 0 次方 => 1 => 字符串为 a
// 第 1 次字符串长度为 2 的 1 次方 => 2 => 字符串为 ab
// 第 2 次字符串长度为 2 的 2 次方 => 4 => 字符串为 abbc
// 第 3 次字符串长度为 2 的 3 次方 => 8 => 字符串为 abbcbccd
// 第 4 次字符串长度为 2 的 4 次方 => 16 => 字符串为 abbcbccdbccdcdde
// 每一步对整个字符串“复制+字母后移”相当于把原始序列分成左右两半，右半是左半中每个字符 +1 的结果。
// 没懂: 把下标 k-1 用二进制表示(例如k=5,k-1=4,二进制:0100)，二进制位从高到低依次对应每一次“是否进入右半”
// 进入右半则需要字母 +1，进入左半字母不变.

// __builtin_popcount 计算无符号整数二进制中 1 的个数
            return char('a' + __builtin_popcount(k - 1));
        }
};

int main() {
    Solution s;
    char result = s.kthCharacter(5);
    std::cout << result << std::endl;
}