【位运算】338. Counting Bits

云水谣CS

于 2018-04-26 20:49:38 发布

阅读量278

点赞数

分类专栏： LeetCodeView

本文链接：https://blog.csdn.net/leetcodecl/article/details/80099578

版权

LeetCodeView 专栏收录该内容

72 篇文章

订阅专栏

本文介绍了一种利用位操作高效计算整数中1的个数的方法。通过观察发现，任意整数左移一位后，其二进制表示中1的个数不变，并且变为偶数；而奇数则是在前一位偶数的基础上末位添加1。基于这一特性，我们可以通过递推的方式快速计算从0到指定整数中每个数1的个数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

任意一个整数左移一位后，1的个数不变，而且扩大一倍，变为偶数（末位必定为0），因此偶数中1的个数等于偶数的一半的数中1的个数；

对于奇数而言，末位必定为1，相当于前一位的偶数在末位添加一个'1'

vector<int> countBits(int num) {
        vector<int> table;
        table.push_back(0);
        for(int i=1;i<=num;i++)
        {
            if(i%2==0)
                table.push_back(table[i/2]);
            else
                table.push_back(1+table[i/2]);
        }
        return table;
        
    }