代码编织梦想

2429. 最小 XOR

给你两个正整数 num1 和 num2 ,找出满足下述条件的整数 x :

  • x 的置位数和 num2 相同,且
  • x XOR num1 的值 最小

注意 XOR 是按位异或运算。

返回整数 x 。题目保证,对于生成的测试用例, x 是 唯一确定 的。

整数的 置位数 是其二进制表示中 1 的数目。

示例 1:

输入:num1 = 3, num2 = 5
输出:3
解释:
num1 和 num2 的二进制表示分别是 0011 和 0101 。
整数 3 的置位数与 num2 相同,且 3 XOR 3 = 0 是最小的。

示例 2:

输入:num1 = 1, num2 = 12
输出:3
解释:
num1 和 num2 的二进制表示分别是 0001 和 1100 。
整数 3 的置位数与 num2 相同,且 3 XOR 1 = 2 是最小的。

思路:
    num & (num-1) 将num的最后一位1变成0
    num | (num+1) 将num的最后一位0变成1

    x的二进制表示中1的数目和num2相同,且要求x异或num1的值最小。
    当x和num1相等时,异或的值最小,为0。
    若num2中有k个1,那么“x异或num1的值最小”等价于————将num1中的k位反转(1变0,0变1)所得的最小值。
    运用“贪心思想”,要让反转后的值最小,num1中高位的1就要变成0,如果k比num1中1的个数还多,那么就要让num1中低位的0变成1,这样得到的值最小。
    直接在num1上进行改动,得到x:num1中1的个数为c1,num2中1的个数为c2,如果c1>c2,就将num1最低的c1-c2个1变成0;如果c1<c2,就将num1最低的c2-c1个0变成1。

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int num1Count=0;
        int num2Count=0;
        int temp1=num1;
        int temp2=num2;
        while(temp1)//num1中1的个数
        {
            temp1=temp1&(temp1-1);
            num1Count++;
        }
        while(temp2)//num2中1的个数
        {
            temp2=temp2&(temp2-1);
            num2Count++;
        }
        while(num1Count>num2Count)//如果c1>c2,就将num1最低的c1-c2个1变成0
        {
            num1=num1&(num1-1);
            num2Count++;
        }
        while(num1Count<num2Count)//如果c1<c2,就将num1最低的c2-c1个0变成1
        {
            num1=num1|(num1+1);
            num1Count++;
        }
        return num1;
    }
};

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_50437588/article/details/127158154

codeforces 76 d.plus and xor(位运算)_v5zsq的博客-爱代码爱编程

Description 给出两整数 A,B A , B A,B,要求找到 X,Y

c++ 算法篇 位运算_流年llyz的博客-爱代码爱编程_c++位运算

 学习目标  1. 理解与掌握 C++ 中的位运算。  2. 灵活应用位运算优化程序。 任何信息在计算机中都是采用二进制表示的,数据在计算机中是以补码形式存储的,位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作,不需要转换成十进制,因此处理速度非常快,在信息学竞赛中往往可以优化理论时间复杂度的系数。同时,一个整数的各个二

codeforces:C. Ternary XOR-爱代码爱编程

传送门 C. Ternary XOR 题意 题意给出一个x的三元组,x的第一个数字必须是2,求出两个三元组a和b,使得 a ⨀ b

【算法总结】最小异或生成树-爱代码爱编程

最小异或生成树 一、前置知识: 1.Trie树: 高效的存储和查找字符串集合的数据结构 int son[maxn][26],cnt[maxn],idx; void add(char *str){///将新的字符串插入到字典树里 int p=0,len=strlen(str); for(int i=0;i<len;i++)

Java BigInteger类| xor()方法与示例-爱代码爱编程

BigInteger类的xor()方法 (BigInteger Class xor() method) xor() method is available in java.math package. xor()方法在java.math包中可用。 xor() method is used to perform xor operation betwe

算法篇:位运算-爱代码爱编程

目录 位运算常见的位运算1 按位与2 按位或3 按位取反4 按位异或5 按位同或6 左移7 带符号右移8 无符号右移编程语言中的位运算嵌入式常用的位运算操作位的二进制形式输出位置位位清零取a为1,b为0的位位逆序常规逆序蝴蝶算法位循环移动lowbit运算lowbit概念lowbit运算的实现消去lowbit求一个二进制数所包含的1的个数 文章最后编

educoder 二进制数据的位运算_二进制与位运算实用操作汇总(基础篇)-爱代码爱编程

位运算是最高效而且占用内存最少的算法操作,但也是最难看懂的操作。然而,关于位运算的用法,笔者查了许多资料,似乎都没有找到详细而系统的讲解资料。笔者对位运算的操作相当感兴趣,因此斗胆尝试对位运算来一个的总结。 本文先从基本概念出发,然后从基本概念推导出基础应用,然后再到算法题实战。层层推进,逐步迭代。 本人水平有限,如有勘误,敬请指正。 说明:本文

易语言 位异或c,易语言教程位运算命令(位取反、位于、位或、位异或)-爱代码爱编程

比特位 比特位就是转换成二进制之后每一位数,bit中文名称是位,音译“比特”,是用以描述电脑数据量的最小单位。 bit 来自binary digit (二进制数字) 二进制数系统中,每个0或1就是一个位(bit)。 1是1,2是10 1的第一个比特位的值是1 2的第一个比特位的值是0,第二个比特位的值是1(从右往左)。2要用两个比特位。

LeetCode—5756. 两个数组最小的异或值之和(Minimum XOR ...)[困难]—分析及代码(Java)-爱代码爱编程

LeetCode——5756. 两个数组最小的异或值之和[Minimum XOR Sum of Two Arrays][困难]——分析及代码[Java] 一、题目二、分析及代码1. 状态压缩 + 动态规划(1)思路(2)代码(3)结果三、其他 一、题目 给你两个整数数组 nums1 和 nums2 ,它们长度都为 n 。 两个数组的 异或值

Codeforces1554C Mikasa (思维 位运算)-爱代码爱编程

题目链接: Mikasa 大致题意 给定非负整数 n n n和 m

异或运算 ^(xor)小解-爱代码爱编程

PS:这里用 ^ 表示异或运算,用 ^ 表示幂,为了方便观察,整数的二进制序列只用4位 什么是异或运算:         设a=1,b=3; 那么a=0001,b=0011         a^b=0001^0011=0010,当两个数做异或运算的时候对应的位置,如果相同则为0,不同则为1,就是说1^1=0,0^0=0 但是 1^0=1;

Leetcode题解-算法-位运算(Python版)-爱代码爱编程

文章目录 1 统计两个数二进制位多少位不同2 数组中唯一一个不重复的数3 寻找数组中缺失的数4 不重复的两个数字5 判断一个数是不是 2 的 n 次方6 判断一个数是不是 4 的 n 次方7 查看整数二进制位 0 和 1 是否交替出现 1 统计两个数二进制位多少位不同 461. 汉明距离(Easy) 方法一:移位实现位计数 两数异或,不同的

位运算练习-力扣645. 错误的集合_狂徒张三三的博客-爱代码爱编程

集合 s 包含从 1 到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复 。 给定一个数组 nums 代表了集合 S 发生错误后的结果。 请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。 来源:力扣(LeetCode) 链接:https:

leetcode50天刷题计划第二季(day 8 —恢复二叉搜索树(17.30-18.40_国际知名观众的博客-爱代码爱编程

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、题目恢复二叉搜索树示例提示进阶 二、思路三、代码 前言 最近跟二叉搜索树杠上了、、 一、题目 恢复二