首页 > 其他分享 >位位运算 方法记录

位位运算 方法记录

时间:2022-10-09 19:14:17浏览次数:56  
标签:运算 记录 位位 wei 010 011 int 100 include



题解

位运算简单理解:

and(&):有假则假;
or(|):有真则真;

不妨从输入样例入手,看看能有什么发现。

举几个例子:

1(001) & 2(010) == 3(011)
1(001) | 2(010) == 0(000)

2(010) & 3(011) == 3(011)
2(010) | 3(011) == 2(010)

3(011) & 4(100) == 7(111)
3(011) | 4(100) == 0(000)

4(100) & 5(101) == 5(101)
4(100) | 5(101) == 4(100)

先观察每组等式两边十进制数和的情况,我们得出第一个结论:

a + b == a & b + a | b

再观察每组等式两边二进制数每一位的情况,我们得出第二个结论:

a、b二进制中每一位上0、1的个数==a & b、a | b二进制中每一位上0、1的个数

解释一下,以下面这两个数为例。

3(011) & 4(100) == 7(111)
3(011) | 4(100) == 0(000)

3(011) 4(100) vs 7(111) 0(000)

然后设计程序就很轻松了。

首先,用类似桶的思想将每一位上\(1\)的个数存下来。

然后,为了使最终生成的数尽可能大,我们从最高位开始遍历。遇到一位存在\(1\)的,我们便由那一位接着向低位遍历,若该位存在\(1\)则为当前生成数增加\(1<<(j-1)\)(\(j\)是遍历到的位),并消耗一个当前位上\(1\)的数量。由此我们可以生成一个数。

最后,求所有生成数的平方和即可。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=100005;
int n;
int wei[200];
ll num[1000000];//num存了所有生成的数,必须开得足够大 
ll ans;
int main()
{
	//freopen("wei.in","r",stdin);
	//freopen("wei.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,x,y,cnt;i<=n;i++)
	{
		cnt=0;
		scanf("%d",&x);
		y=x;
		while(y!=0)
		{
			wei[++cnt]+=y%2;//wei[i]存第i位上1的个数和
			y>>=1;
		}
	}
	int cnt=0;
	for(int i=20;i>=1;i--)
		while(wei[i]!=0)
		{
			cnt++;
			for(int j=i;j>=1;j--)
				if(wei[j]!=0)
				{
					num[cnt]+=1<<(j-1);//为生成数作贡献
					wei[j]--;//消耗当前位上的1
				}
		}
	for(int i=1;i<=cnt;i++)
		ans+=1ll*num[i]*num[i];
	printf("%lld",ans);
	return 0;
}

标签:运算,记录,位位,wei,010,011,int,100,include
From: https://www.cnblogs.com/fish4174/p/16773316.html

相关文章

  • 【博学谷学习记录】超强总结,用心分享 。多线程相关点知识学习。
    一、实现多线程1.1了解多线程多线程是指从软件或硬件上实现多个线程并发执行的技术。具有多线程能力的计算机因有硬件支持而能够在同一时间执行多个线程,提......
  • python调用c++的方法,加速运算
    cpp源代码#include"iostream"usingnamespacestd;classCalc{public:intadd(inta,intb);};intCalc::add(inta,intb){cout<<"收到参数为a,b:"<<a<......
  • 位位运算 方法记录
    题解我们首先来分析小朋友的三个指标:手里的数,特征值,分数。手里的数:即我们输入的长度为\(n\)的序列;特征值:从第一个小朋友到当前小朋友的手上的数的最大子段和;分数......
  • 【博学谷学习记录】超强总结,用心分享|MySql连接查询超详细总结
    一、概述在实际开发中,大部分情况下都不是在单表中进行数据操作,一般都是多张表进行联合查询。通常一个业务就会对应的有好几张表。MySql中的连接查询分为交叉连接,内连......
  • uniapp--微信小程序 问题记录
    自动适配问题rem适配为什么选择rema)机型太多,不同的机型屏幕大小不一样b)需求:一套设计稿的内容在不同的机型上呈现的效果一致,根据屏幕大小不同的变化,页面中的内......
  • let、const命令(学习阮一峰ES6记录)
    1.let命令ES6新增let命令,作用和var类似,用来声明变量,但是let只能在所在代码块(区域)中使用。例:1{2leta=2;3varb=3;4}5console.log(a)//aisn......
  • docker部署项目注意事项记录
    1.不同容器之前通信,如前端容器与后端容器,需要注意配置文件(如前端nginx的nginx.conf,后端的application.yml)里的ip地址要为宿主机的具体ip,如192.168.0.12,而不能为loca......
  • 记录Linux下启动docker中Mysql,并进入mysql。
    1.启动dockersystemctlstartdocker  2.查看docker容器启动信息,并找到mysql容器  3.使用进程名启动mysql:dockerstartmysql-test;也可以使用进程id启动:docker......
  • java---了解以下运算符
    了解即可1&2用于条件判断,&条件1和2都执行1&&2,条件1判断错误的情况下,条件2不执行&当运算符的化,例如4&7,两者上下对比都是1则为1,反之为0,结果就是二进制100也就是......
  • 快速幂,位运算,pow()函数
    位运算:位运算可以用来查找01二进制串中1或0的个数,同时也可以实现幂的计算,但是只能是以2为底的幂运算统计字符串中1的个数#include<bits/stdc++.h>usingnamespacestd;......