的数字的位差之和给定数字 N ，任务是计算从 0 到 N 的每个连续数字的二进制表示中相应的不同位 总计。
示例：
输入： N = 5
输出： 8
解释：
数字的二进制表示形式为：
0 -> 000, 1 -> 001 ,
2 -> 010,
3 -> 011,
4 -> 100,
5 -> 101
1 和 0 之间 -> 1 位不同
Be补间2并且 1 -> 2 位不同
3 和 2 之间 -> 1 位不同
4 和 3 之间 -> 3 位不同
5 和 4 之间 -> 1 位不同
总计 = 1 + 2 + 1 + 3 + 1 = 8
输入： N = 11
输出： 19
朴素的方法：其想法是从0迭代到N，并且对于每个连续的元素对，使用本文中讨论的方法为每对找到不同的数字位数。
时间复杂度： O(N* log N)
辅助空间：(1)
高效方法：高效方法，必须注意以下几点：
数量: 1 2 3 4 5 6 7 8
位_差异：1 2 1 3 1 2 1 4
总和差异：1 3 4 7 8 10 11 15
通过以上计算，我们可以观察到：
sum_diff = (2x+1-1)
其中 x = log2(N)
N = 2a + 2b + … + 2x
因此，从0到N对应的不同位之和可计算为：
sum_diff = (2a+1-1) + (2b+1-1) + … + (2x+1-1) ).
一些示例：
如果 N = 8，则
8 的二进制表示为“1000”
因此 11 = 23
总计数 = (23+1 – 1)
总计数 = 8 – 1 = 7。
如果 N = 11，则
11 的二进制表示为“1011”
因此 11 = 23 + 21 + 20
=> 总计数 = (23+1 – 1) + (21+1 – 1) + (20+1 – 1)
=> 总计数 = 15 + 3 + 1 = 19.
以下是上述方法的实现：
//上述方法的C++程序
#包括
使用命名空间 std；
// 快速实现的函数
// 求幂
int binpow(int a, int b)
{
整数分辨率=1；
而（b）{
如果 (b & 1)
资源 = 资源 * a;
一个=一个*一个；
b / = 2;
}
返回资源；
}
// 返回值的函数
// 2 的幂
int 查找（int x）
{
如果（x==0）
返回0；
int p = log2(x);
返回 binpow(2, p + 1) - 1;
}
// 将 N 转换为二进制的函数
字符串 getBinary(int n)
{
// 存储二进制表示
字符串 ans = "";
// 迭代n的每一位数字
而（n）{
int 挖掘 = n % 2;
ans += to_string(dig);
n /= 2；
}
// 返回二进制表示
返回答案；
}
// 查找位差异的函数
int 总计数差异(int n)
{
// 获取二进制表示
字符串 ans = getBinary(n);
// 总位数
// 0 到 N 的差异
int 请求 = 0;
// 迭代每个二进制位
for (int i = 0; i < ans.size(); i++) {
// 如果当前位为“1”，则添加
//当前位的计数
if (ans[i] == '1') {
req += find(binpow(2, i));
}
}
返回请求；
}
// 驱动程序代码
int main()
{
// 给定数字
整数 N = 5；
// 函数调用
cout << 总计数差异(N);
返回0；
} //上述方式的Java程序
导入www.sychzs.cn.*；
导入java.lang.Math；
GFG类{
// 快速实现的函数
// 求幂
静态 int binpow(int a, int b)
{
整数分辨率=1；
而 (b > 0)
{
如果（b％2==1）
资源 = 资源 * a;
一个=一个*一个；
b / = 2;
}
返回资源；
}
// 返回的函数
// 2 的幂值
静态 int 查找（int x）
{
如果（x==0）返回0；
int p = (int)(Math.log(x) / Math.log(2));
返回 binpow(2, p + 1) - 1;
}
// 将 N 转换为二进制的函数
静态字符串 getBinary(int n)
{
// 存储二进制表示
字符串 ans = "";
// 迭代n的每一位数字
而 (n > 0)
{
int 挖掘 = n % 2;
ans += 挖掘；
n /= 2；
}
// 返回二进制表示
返回答案；
}
// 查找位差异的函数
静态 int TotalCountDifference(int n)
{
// 获取二进制表示
字符串 ans = getBinary(n);
// 总位数
// 0 到 N 的差异
int 请求 = 0;
// 迭代每个二进制位
for(int i = 0; i < ans.length(); i++)
{
// 如果当前位为“1”，则添加
//当前位的计数
if (ans.charAt(i) == '1')
{req += find(binpow(2, i));
}
}
返回请求；
}
// 驱动代码
公共静态无效主（字符串[]参数）
{
// 给定数字
整数 n = 5；
System.out.print(totalCountDifference(n));
}
}
// 此代码由 spp____#上述方法的Python3程序
从数学导入日志
# 快速实现的函数
# 求幂
def binpow(a, b):
分辨率=1
而（b > 0）：
如果（b％2==1）：
分辨率 = 分辨率 * a
一个=一个*一个
b //= 2
返回资源
# 返回值的函数
# 2 的幂
def 查找(x):
如果（x==0）：
返回0
p = log(x) / log(2)
返回 binpow(2, p + 1) - 1
# 将 N 转换为二进制的函数
def getBinary(n):
# 存储二进制表示
答案=“”
# 迭代n的每一位数字而（n>0）：
挖掘 = n % 2
ans += str(挖)
n //= 2
# 返回二进制表示
返回答案
# 查找位差异的函数
def 总计数差异(n):
# 获取二进制表示
ans = getBinary(n)
# 总位数
# 从 0 到 N 的差异
要求= 0
# 迭代每个二进制位
对于范围内的 i(len(ans))：
# 如果当前位为“1”，则添加
# 当前位的计数
if (ans[i] == '1'):
请求 += 查找(binpow(2, i))
返回请求
# 驱动程序代码
# 给定数字
数 = 5
# 函数调用
print(总计数差异(N))
# 此代码由 shubhamsingh10//上述方法的C#程序
使用系统；
GFG类{
// 快速实现的函数
// 求幂
静态 int binpow(int a, int b){
整数分辨率=1；
而 (b > 0)
{
如果（b％2==1）
资源 = 资源 * a;
一个=一个*一个；
b / = 2;
}
返回资源；
}
// 返回的函数
// 2 的幂值
静态 int 查找（int x）
{
如果（x==0）
返回0；
int p = (int)(Math.Log(x) / Math.Log(2));
返回 binpow(2, p + 1) - 1;
}
// 将 N 转换为二进制的函数
静态字符串 getBinary(int n)
{
// 存储二进制表示
字符串 ans = "";
// 迭代n的每一位数字
而 (n > 0)
{
int 挖掘 = n % 2;
ans += 挖掘；
n /= 2；
}
// 返回二进制表示
返回答案；
}
// 查找位差异的函数
静态 int TotalCountDifference(int n)
{
// 获取二进制表示
字符串 ans = getBinary(n);
// 总位数// 0 到 N 的差异
int 请求 = 0;
// 迭代每个二进制位
for(int i = 0; i < ans.Length; i++)
{
//如果当前位为'1'则添加
// 当前位数
如果 (ans[i] == '1')
req += find(binpow(2, i));
} }
返回请求；
}
// 驱动代码
公共静态无效Main（）
{
// 给定数字
整数 n = 5；
Console.Write(totalCountDifference(n));
}
}
// 此代码由 Nidhi_biet8
时间复杂度： O((log N) 2 )
辅助空间： (1)
如果您想参加行业专家的现场课程，请参阅《 Geeks现场课程》和《 Geeks现场课程美国》。
