本文主要是介绍ACdream1154(lowbit的理解)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
for(int i = 1; i <= n; i ++)
ans += lowbit(i)
lowbit(i)的意思是将i转化成二进制数之后，只保留最低位的1及其后面的0，截断前面的内容，然后再转成10进制数
比如lowbit(7),7的二进制位是111，lowbit(7) = 1
6 = 110(2),lowbit(6) = 2,同理lowbit(4) = 4,lowbit(12) = 4,lowbit(2) = 2,lowbit(8) = 8
每输入一个n，求ans
Input
多组数据，每组数据一个n(1 <= n <= 10^9)
Output
每组数据输出一行，对应的ans
Sample Input
1
2
3
Sample Output
1
3
4
解题思路：
这道题考查的是对树状数组lowbit的深入理解。首先题意并不难懂，直接暴力或者lowbit打表的话都行不通。
换种思路，把它当成数学题来做。可以先把1~15的lowbit值打出来
可以发现规律，奇数位的lowbit值都为1。如果我们下次把偶数位的lowbit值全部取出来，都除以2
你会发现这原来这可以递归。这样一直递归下去，就可以求解。最后需要注意的是n分奇偶两种情况：1.当n为奇数时，第一次n / 2后原来奇数的数量其实是少1的，所以最后要把1加回来；2.当n为偶数时，第一次n / 2分成的两部分正好没有缺漏，所以最后不作处理。
给出公式res( n ) = 2 * res ( n / 2) + n / 2 + ( n & 1) // (n & 1)操作等价于(n % 2) ，作为判断n的奇偶用，奇数时加1，偶数加0
例如：当n == 5时，1~5对应的lowbit值分别为1,、2、1、4、1，第一次分时，原来奇数的那部分明明有3个1，但被n / 2弄成了2，所以计算结束后要加回来；同理，当n== 4时，因为第一次分时就没有缺漏，所以最后不处理。我们为什么只考虑第一次呢，因为缺漏值可能出现在第一次，以后的分割不会造成缺漏。
完整代码：
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;/** Constant List .. **/ //{const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;LL dp(int n)
{if(n == 1)return 1;LL res = 2 * dp(n >> 1) + n / 2;if(n & 1)res ++;return res;
}int main()
{#ifdef DoubleQfreopen("in.txt" , "r" , stdin);#endif;int n;while(~scanf("%d",&n)){printf("%lld\n",dp(n));}
}
这篇关于ACdream1154(lowbit的理解)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
