找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 671|回复: 2
收起左侧

[资源分享] 20: XOR Sum

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-4-2015 12:53 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

问题可以转化为统计1~N这N个数中,每一个位上一共出现了多少次1,对于一个数x,其每一位上出现1的个数用f(x)表示,如果其为1的最高bit是n,则有f(x) = f((1<<n)-1) + f((x^(1<<n))+1),其中+表示统计结果的对应项相加
  1. #include <vector>
  2. using std::vector;

  3. class Solution {
  4. public:
  5.         typedef long long LL;
  6.         static const int MAX = 60;
  7.         static const LL  ONE = 1;
  8.         void count(vector<LL>& c, LL x){
  9.                 if(!x) return;
  10.                
  11.                 int n = 0;
  12.                 for(int i = 0; i < MAX; ++i){
  13.                         if(x & (ONE << i)) n = i;
  14.                 }
  15.                 LL y = x ^ (ONE << n);
  16.                 c[n] += y + 1;
  17.                 for(int i = 0; i < n; ++i){
  18.                         c【i】 += ONE << (n-1);
  19.                 }
  20.                 count(c, y);
  21.         }
  22.         long long xorSum(long long x) {
  23.                 vector<LL> c(MAX, 0);
  24.                 count(c, x);
  25.                 LL res = 0;
  26.                 for(int i = 0; i < MAX; ++i){
  27.                         if(c【i】 & 1) res |= ONE << i;
  28.                 }
  29.                 return res;
  30.         }
  31. };
复制代码


评分

参与人数 1金钱 +2 收起 理由
Sophia + 2 赞一个!

查看全部评分

发表于 10-4-2015 10:47 PM | 显示全部楼层
赞赞的~~~下次我们会举办一次测试代码运行速度的比赛~~~欢迎参加~~大米送上~~~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

0

主题

0

精华

23

积分

新米人

Rank: 1

积分
23
发表于 9-25-2016 02:27 AM | 显示全部楼层
nice
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表