位运算之妙用:识别独特数字(寻找单身狗)

2024-02-03 18:28

本文主要是介绍位运算之妙用:识别独特数字(寻找单身狗),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

找单身狗1

图解:

代码如下:

找单身狗2

图解:

代码如下:


寻找单身狗1

从数组中 的1 2 3 4 5 1 2 3 4 中找出没有另一个相同的数与其匹配的数

这个问题的原理是利用异或运算的性质。异或运算(XOR)是一种二进制运算,其特点是相同为0,不同为1。在这个问题中,数组arr中的所有元素都出现了两次,只有一个元素只出现了一次。通过异或运算,可以将出现两次的元素抵消掉,最后剩下的就是只出现一次的元素。

具体步骤如下:

  1. 初始化一个变量n为0,用于存储异或结果。
  2. 遍历数组arr,将每个元素与n进行异或运算,并将结果赋值给n。
  3. 遍历结束后,n的值就是只出现一次的元素。

  图解:

 代码如下:

//找单身狗1
int main()
{int n = 0;int arr[9] = { 1,2,3,4,5,1,2,3,4 };for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++){n = n ^ arr[i];//任何数和0异或就得到自己,与自己异或则为0}printf("%d", n);

寻找单身狗2

一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

例如:

有数组的元素是:1,2,3,4,5,1,2,3,4,6

只有5和6只出现1次,要找出5和6.

        找出一个只出现过一次的数字的问题处理方法就是找一个数字把里面所有的数字都异或一遍,利用异或两次等于没异或的特点来处理。那么如果有两个数字都只出现了一次,那么如此得到的应该是两个数异或的结果。首先这个结果肯定不是0(要不然就全都配对了),所以里面一定至少一位是一。找出值为1的一位,以这一位的值将结果分为两组。例如1 2 3 4 1 2,异或完的结果应该是3^4得到的111,那么随便找一位就行了。例如找最低位,那么这一位是1的有1 3 1,是0的有2 4 2,由于是利用异或结果为1的某一位分的组,所以两个待查询数字一定分别在两组中。所以再找两个变量,分别异或两组数,即可找到这两个数。

图解:

代码如下:


//找单身狗2
//1 2 3 4 5 1 2 3 4 6//pnum1 和 pnum2 存储 你找到的这两个数据 n代表数组长度
void FindNum(int arr[], int len, int* pnum1, int* pnum2)
{//1.将整个数组异或起来,得到两个不同数字的异或结果 例如: 5^6int tmp = 0;for (int i = 0; i < len; i++){tmp ^= arr[i];}//2.找到tmp中,二进制为1的某一位k 0110 0111 0001int k = 0;for (int i = 0; i < 32; i++){if ((tmp >> i) & 1 != 0){k = i;break;}}//3、遍历数组 把每个数据 第K为上是1的,分到一个组进行异或//最终的值存储到 pnum1 或者 pnum2 当中*pnum1 = *pnum2 = 0;for (int i = 0; i < len; i++){if ((arr[i] >> k) & 1 != 0){//第k位是1*pnum1 ^= arr[i];}else{	//第k位是0*pnum2 ^= arr[i];}}
}int main()
{int arr[] = { 1,2,3,4,5,1,2,3,4,6 };int len = sizeof(arr) / sizeof(arr[0]);int num1 = 0;int num2 = 0;;FindNum(arr, len, &num1, &num2);printf("%d %d", num1, num2);return 0;
}

希望对你有帮助!加油!

若您认为本文内容有益,请不吝赐予赞同并订阅,以便持续接收有价值的信息。衷心感谢您的关注和支持!

这篇关于位运算之妙用:识别独特数字(寻找单身狗)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/674994

相关文章

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

阿里开源语音识别SenseVoiceWindows环境部署

SenseVoice介绍 SenseVoice 专注于高精度多语言语音识别、情感辨识和音频事件检测多语言识别: 采用超过 40 万小时数据训练,支持超过 50 种语言,识别效果上优于 Whisper 模型。富文本识别:具备优秀的情感识别,能够在测试数据上达到和超过目前最佳情感识别模型的效果。支持声音事件检测能力,支持音乐、掌声、笑声、哭声、咳嗽、喷嚏等多种常见人机交互事件进行检测。高效推

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

寻找身高相近的小朋友

题目描述: 小明今年升学到小学一年级,来到新班级后发现其他小朋友们身高参差不齐,然后就想基于各小朋友和自己的身高差对他们进行排序,请帮他实现排序。 输入描述: 第一行为正整数H和N,0<H<200,为小明的身高,0<N<50,为新班级其他小朋友个数。第二行为N个正整数H1-HN,分别是其他小朋友的身高,取值范围0<Hi<200(1<=i<=N),且N个正整数各不相同。 输出描述: 输出

AIGC6: 走进腾讯数字盛会

图中是一个程序员,去参加一个技术盛会。AI大潮下,五颜六色,各种不确定。 背景 AI对各行各业的冲击越来越大,身处职场的我也能清晰的感受到。 我所在的行业为全球客服外包行业。 业务模式为: 为国际跨境公司提供不同地区不同语言的客服外包解决方案,除了人力,还有软件系统。 软件系统主要是提供了客服跟客人的渠道沟通和工单管理,内部管理跟甲方的合同对接,绩效评估,BI数据透视。 客服跟客人

【Java中的位运算和逻辑运算详解及其区别】

Java中的位运算和逻辑运算详解及其区别 在 Java 编程中,位运算和逻辑运算是常见的两种操作类型。位运算用于操作整数的二进制位,而逻辑运算则是处理布尔值 (boolean) 的运算。本文将详细讲解这两种运算及其主要区别,并给出相应示例。 应用场景了解 位运算和逻辑运算的设计初衷源自计算机底层硬件和逻辑运算的需求,它们分别针对不同的处理对象和场景。以下是它们设计的初始目的简介:

位运算:带带孩子吧,孩子很强的!

快速进制 在聊到位运算之前,不妨先简单过一遍二进制的东西。熟悉二进制和十进制的快速转换确实是掌握位运算的基础,因为位运算直接在二进制位上进行操作。如果不熟悉二进制表示,很难直观理解位运算的效果。 这里主要涉及二进制和十进制之间的互相转换。 十进制转二进制 十进制转二进制可以使用常见的 除2取余法 进行。每次将十进制除以2并记录所得余数,直到商为0,然后再将记录的余数 从下往上排列即