当前位置：首页 > news >正文

【Leetcode】取余/2的幂次方

news 来源：原创 2025/6/3 0:16:02

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

示例 1:
输入: num = 38
输出: 2
解释:
各位相加的过程为：
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
由于 2 是一位数，所以返回 2。

示例 2:
输入: num = 0
输出: 0

进阶：你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

代码1
递归：

class Solution {public int addDigits(int num) {int sum=0;if(num<=9){return num;}while(num>0){sum+=num%10;num/=10;}return addDigits(sum);}
}

代码2
循环迭代

class Solution {public int addDigits(int num) {while (num >= 10) {int sum = 0;while (num > 0) {sum += num % 10;num /= 10;}num = sum;}return num;}
}

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

代码1

class Solution {public boolean isPowerOfTwo(int n) {if (n <= 0) return false; // 2的幂一定是正数while (n % 2 == 0) {n /= 2; // 不断除以2}return n == 1; // 如果最终结果是1，说明是2的幂}
}

代码2

public boolean isPowerOfTwo(int n) {return n > 0 && (n & (n - 1)) == 0;}

说明:

& 运算符的完整详解
1. 基本定义
& 是 Java 中的 按位与（Bitwise AND） 运算符，它对两个整数的二进制形式的每一位进行逻辑与运算。
**2. 运算规则（逐位计算）**对于每一对二进制位：

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

3. 实际计算示例
假设 a = 5，b = 3，计算 a & b：

a = 5 → 二进制 0101
b = 3 → 二进制 0011
a & b → 0001 (十进制 1)

4. 关键特性
清零特技：
x & 0 = 0（任何数与 0 按位与，结果都是 0）
保留特技：
x & 1 = x（保留最低位，其他位清零)
5. 经典应用场景
(1) 判断奇偶

boolean isOdd = (n & 1) == 1;// true表示奇数

原理：二进制最后一位为 1 则是奇数。
(2) 检查2的幂

boolean isPowerOfTwo = (n & (n - 1)) == 0;

原理：2的幂的二进制只有1个1。
(3) 取最低位的1

int lowestOne = n & (-n);

原理：补码特性保留最低位的1。

位运算判断 2 的幂次方（超详细解析）
1. 核心思路
2 的幂次方的二进制表示有一个
关键特征：-所有 2 的幂次方的数，其二进制形式都是 1 后面跟着若干个 0。
例如：
1 → 0001
2 → 0010
4 → 0100
8 → 1000
2. 关键位运算技巧
利用以下位运算性质：
n & (n - 1) 的作用：
去掉二进制数 n 的最低位 1。
例如：
n = 8（1000），
n - 1 = 7（0111）
1000 & 0111 = 0000（结果是 0）
3. 判断条件
如果 n 是 2 的幂次方，则必须满足：
n > 0（2 的幂次方一定是正数）。
n & (n - 1) == 0（二进制中只能有 1 个 1）。
4. 代码实现

 public boolean isPowerOfTwo(int n) {return n > 0 && (n & (n - 1)) == 0;}

相关文章：