当前位置: 首页 > article >正文

力扣每日一题 3226. 使两个整数相等的位更改次数

给你两个正整数 n 和 k

你可以选择 n 的 二进制表示 中任意一个值为 1 的位,并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现,返回 -1。

又是一个简单题,直接n和k转换成二进制然后算就可以了。

不过我们可以用位运算再提一下速度。

首先判断能否更改。可以用n&k计算。与是两个同为1则1否则为0,那么就应该是n&k=k

已经保证了所有k为1时n都为1,那么统计一下n和k有多少位不同就可以了。我们可以计算n^k中1的个数。如果还是转二进制计算的话那我们位运算就纯画蛇添足了。幸好即使是C/C++也有办法可以快速统计1的个数,那就是__builtin_popcount。(这种内建函数拥有硬件支持,比手动逐位计算更快。) 内建函数的实现依赖于编译器,可能是直接一句popcnt了事,也可能是其他各种方式实现计算。

int minChanges(int n, int k) {
    return (n & k) != k ? -1 : __builtin_popcount(n ^ k);
}

C语言的高光时刻,一行解决问题。同样的,C++也可以用。

再贴个python的

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        return -1 if n & k != k else (n ^ k).bit_count()

顺便补充几个内置的二进制操作函数

GCC 和 Clang 提供了几个内建的二进制操作函数,常用于位运算优化:

1. **`__builtin_popcount(x)`**:计算整数 `x` 的二进制中“1”的个数。
2. **`__builtin_clz(x)`**:计算 `x` 前导零的个数(未指定负数行为)。
3. **`__builtin_ctz(x)`**:计算 `x` 尾随零的个数。
4. **`__builtin_parity(x)`**:计算 `x` 的二进制中“1”的个数是否为奇数,返回 1 表示奇数个,0 表示偶数个。

这些函数支持 `int`、`long` 和 `long long`,只需在后加 `l` 或 `ll` 后缀(如 `__builtin_popcountll`)。

这些内建函数通常能够利用底层硬件指令进行优化。现代处理器一般有专门的指令支持二进制位操作,例如:

- **`__builtin_popcount`** 可以使用处理器的 **POPCNT** 指令。
- **`__builtin_clz`** 和 **`__builtin_ctz`** 可使用 **LZCNT** 和 **TZCNT** 指令。

这些指令直接由硬件执行,比手动循环计算快得多,特别是在处理大量数据或频繁位运算时能够显著提升性能。


http://www.kler.cn/a/377690.html

相关文章:

  • 19、鸿蒙学习——配置HDC命令 环境变量
  • tcp_rcv_synsent_state_process函数
  • java 加密算法
  • 基于Springboot + vue实现的火锅店管理系统
  • 【多模态】从零学习多模态——2024学习笔记总结
  • WebP Vs. PNG:哪种图像格式适合您的网站?
  • 建设NFS服务器并实现文件共享
  • 校园社团信息管理:Spring Boot技术的应用与挑战
  • 【系统设计】让 Java “动起来”:动态语言与静态语言的比较及 DSL 实现
  • 继承【C++】
  • Linux入门(2)
  • OpenAI Swarm:多智能体编排框架
  • mysql通过sql语句手动关闭连接
  • rnn/lstm
  • java的批量update
  • SQL,力扣题目1549,每件商品的最新订单【窗口函数】
  • 实现GUI界面中的logo图片的编码与隐藏
  • 基于vue3和elementPlus的el-tree组件,实现树结构穿梭框,支持数据回显和懒加载
  • mfc140u.dll丢失怎么办? mfc140u.dll文件缺失的修复技巧
  • 机器视觉基础—双目相机
  • Python 三维图表绘制指南
  • 一文囊括风控建模中的变量筛选方法
  • Linux 下执行定时任务之 Systemd Timers
  • Vue问题汇总解决
  • 【Centos】在 CentOS 9 上使用 Apache 搭建 PHP 8 教程
  • Vue插槽的使用场景