位运算和进制转换
位运算和进制转换
进制转换方法
在JavaScript中，进行进制转换的方法主要有两种：parseInt() 和 toString()。
| 方法 | 描述 |
|---|---|
parseInt(string, radix) | 将字符串按照指定的进制解析为整数。radix 是可选参数，表示字符串的进制，范围在2到36之间。如果省略radix，或者其值为0，则数字将以10为基础来解析。如果字符串以 "0x" 或 "0X" 开头，则将以16为基数。如果 radix小于2或大于36，parseInt() 将返回 NaN。 |
toString(radix) | 这个方法返回一个表示该对象的字符串 radix是一个介于2到36之间的整数，表示要使用的基数。 如果省略该参数，则默认返回十进制字符串。 |
parseInt()方法
当然，我将通过一些示例来说明 parseInt() 方法在 JavaScript 中的使用。
parseInt() 方法用于解析一个字符串参数，并返回一个指定基数的整数（数学上通常称为“截尾”整数）。它接受两个参数：
string：要解析的值。如果字符串的第一个字符不能被转换成数字，那么parseInt()会返回NaN（表示非数字）。radix：（可选）：表示上述字符串的基数，即该数字原来是什么进制。它的值介于 2（二进制）和 36（包含 0-9 以及 A-Z）之间。如果省略该参数或其值为 0，则数字会根据以下情况解析：- 如果字符串以 "0x" 或 "0X" 开头，则基数为 16（十六进制）。
- 如果字符串以 "0" 开头，则基数为 8（八进制）或 10（十进制），但 ECMAScript 5 规范规定，它应该被解析为十进制。
- 否则，基数为 10（十进制）。
示例 1：基本使用
var decimal = parseInt("10"); // 10（十进制）
console.log(decimal);
示例 2：指定基数
var binary = parseInt("10", 2); // 2（二进制转十进制）
var octal = parseInt("10", 8); // 8（八进制转十进制）
var hex = parseInt("10", 16); // 16（十六进制转十进制）
console.log(binary);
console.log(octal);
console.log(hex);
示例 3：带有前缀的字符串
var hexWithPrefix = parseInt("0x10"); // 16（十六进制，由于前缀 "0x"）
var octalWithPrefix = parseInt("010"); // 8（八进制，但注意在 ES5 中，前缀 "0" 不再总是表示八进制）
console.log(hexWithPrefix);
console.log(octalWithPrefix); // 注意：在严格模式下，这可能会返回 10（十进制），因为 "010" 被视为十进制
示例 4：无法解析的字符串
var notANumber = parseInt("Hello"); // NaN（无法解析为数字）
var alsoNotANumber = parseInt("123abc"); // 123（只解析到第一个无法转换为数字的字符为止）
console.log(notANumber);
console.log(alsoNotANumber);
示例 5：省略基数参数
var autoDecimal = parseInt("10"); // 10（十进制，因为省略了基数参数）
var autoHex = parseInt("0x10"); // 16（十六进制，因为字符串以 "0x" 开头）
console.log(autoDecimal);
console.log(autoHex);
注意事项
- 当使用
parseInt()解析字符串时，务必注意字符串的开头字符以及是否提供了基数参数。这可能会影响解析的结果。 - 在解析可能包含非数字字符的字符串时，务必检查
parseInt()的返回值，以避免意外的NaN或不正确的数字。 - 在处理用户输入或不确定的数据时，建议使用更严格的解析方法，如
Number()构造函数或一元加号运算符+，并准备好处理可能的错误或异常情况。
toString() 方法
toString() 是 JavaScript 中所有对象都继承自 Object.prototype 的一个方法。这个方法返回一个表示该对象的字符串。对于不同的数据类型，toString() 方法的行为可能有所不同。
数字（Number）
对于数字类型，toString() 方法可以将数字转换为字符串。它接受一个可选的参数，即基数（radix），表示转换的进制。如果省略基数，则默认返回十进制字符串。
示例：
var num = 255;
console.log(num.toString()); // "255"
console.log(num.toString(2)); // "11111111" (二进制)
console.log(num.toString(8)); // "377" (八进制)
console.log(num.toString(16)); // "ff" (十六进制)
如果基数不在 2 到 36 之间（包括 2 和 36），则会抛出一个 RangeError。
二进制
二进制数（Binary）：由 00 和 11 两个数码来表示的数。二进制数中每一个 0 或每一个 1 都称为一个「位（Bit）」。
- 十进制数：有 0∼9 共 10 个数字，进位规则是「满十进一」。
- 二进制数: 只有 0 和 1 两个数码，它的进位规则是「逢二进一」。
二进制转换
二进制转十进制数
在十进制数中，数字 2749(10) 可以理解为 2×1000+7×100+4×10+9∗1 ，相当于 2×10^3+7×10^2+4×10^1+9×10 ，即 2000+700+40+9=2749(10) 。
在二进制数中，01101010(2) 可以看作为 (0×2^7)+(1×2^6)+(1×2^5)+(0×2^4)+(1×2^3)+(0×2^2)+(1×2^1)+(0×2^0)(，即 0+64+32+0+8+0+2+0=106(10) 。
十进制转二进制数
十进制数转二进制数的方法是：除二取余，逆序排列法。
以十进制数中的 106(10) 为例。
反向遍历每次计算的余数，依次是 0 、1、1、0、1、0、1、0 即 01101010(2)
function toBinary(num) {
if (num === 0) return '0000'
let remain = 0
let res = []
while (num !== 0) {
remain = num % 2
num = Math.floor(num / 2)
res.push(remain)
}
return res.reverse().join('')
}
二进制转十六进制
在JavaScript中，如果你有一个二进制字符串（比如 '10101101'），并且你想将它转换为16进制数字（而不是字符串）：
- 首先将它转换为一个二进制数值；
- 然后将这个数值转换为16进制。
但是，由于JavaScript中的数字都是基于浮点数标准的，而且它们有精度限制，所以直接操作大二进制字符串作为数字可能会导致精度损失。
不过，对于较小的二进制字符串，你可以使用以下步骤：
- 使用
parseInt将二进制字符串转换为十进制数。 - 使用
toString(16)将十进制数转换为16进制字符串。 - 如果你真的需要16进制数字（而不是字符串），你可以使用
parseInt再次将16进制字符串转换为十进制数（但这通常没有意义，因为你已经有了十进制数）。但如果你想要一个表示16进制数的JavaScript对象（比如一个BigInt），你可以使用BigInt('0x' + hexString)。
但这里我们假设你想要一个16进制字符串，因为这是最常用的格式：
function binaryToHex(binaryString) {
// 确保输入是有效的二进制字符串
if (!/^[01]+$/.test(binaryString)) {
throw new Error('Invalid binary string');
}
// 使用parseInt转换为十进制，并指定基数为2（二进制）
let decimal = parseInt(binaryString, 2);
// 使用toString转换为16进制字符串，并指定基数为16
let hexString = decimal.toString(16).toUpperCase();
// 如果需要前导零以确保长度（例如，总是返回2位数的16进制），可以使用padStart方法
// hexString = hexString.padStart(2, '0'); // 但这通常只用于单个字节（8位）
return hexString;
}
const binary = '10101101';
const hex = binaryToHex(binary);
console.log(hex); // 输出: "AD"
如果你想要一个BigInt对象来表示16进制数（对于非常大的数字），你可以这样做：
function binaryToBigIntHex(binaryString) {
// 确保输入是有效的二进制字符串
if (!/^[01]+$/.test(binaryString)) {
throw new Error('Invalid binary string');
}
// 使用parseInt转换为十进制，并指定基数为2（二进制）
let decimal = parseInt(binaryString, 2);
// 使用BigInt和'0x'前缀创建一个表示16进制数的BigInt对象
let bigIntHex = BigInt(`0x${decimal.toString(16).toUpperCase()}`);
return bigIntHex;
}
const binary = '10101101';
const bigIntHex = binaryToBigIntHex(binary);
console.log(bigIntHex.toString(16)); // 输出: "0xAD" 注意前导零和'0x'前缀
十进制转 n 进制
十进制转n进制的思路：除 n 取余法
思路：
确定基数：
- 首先，你需要知道你要转换到的基数n是多少。
- 基数n决定了你的新数制中有多少个不同的数字符号。例如，在二进制中，n=2，你有0和1两个数字符号；在十六进制中，n=16，你有0-9和A-F（或a-f）共16个数字符号。
初始化结果：
- 开始时，将结果设置为一个空字符串或列表，用于存储转换后的n进制数的每一位。
进行除法：
- 将十进制数除以基数n，得到商和余数。
- 这个余数就是n进制数的最低位。
处理余数：
- 将余数转换为对应的n进制数字符号（如果n>10，可能需要使用字母A-Z或a-z来表示）。
- 将这个符号添加到结果字符串或列表的前面。
更新十进制数：
- 将上一步得到的商作为新的十进制数，重复步骤3和4，直到商变为0。
返回结果：
- 当商变为0时，说明所有的十进制位都已经转换为n进制位。
- 此时，返回结果字符串或列表即可。
function convertToBaseN(num: number, n: number ): string {
if (base < 2 || base > 36) {
throw new Error("基数必须在2到36之间");
}
if (num === 0) return '0'
let result: Array<string> = []
let digist = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
let isNagative = num < 0
num = Math.abs(num)
while (num > 0) {
let remider = num % n
result.push(digist[remider])
num = Math.floor(num / n)
}
if (isNagative) {
result.push('-')
}
return result.reverse().join('')
};
n 进制转十进制
思路
将n进制（其中n是大于1的整数）转换为十进制的过程相对简单。基本思路是，从最低位（右边）开始，每一位上的数字乘以n的相应次幂（从0开始），然后将这些乘积相加。
假设我们有一个n进制的数 A = (an-1 an-2 ... a2 a1 a0)，其中 an-1 是最高位，a0 是最低位（也就是个位）。
转换为十进制的公式为： $$ (A_{十进制} = a_{n-1} \times n^{n-1} + a_{n-2} \times n^{n-2} + \ldots + a_2 \times n^2 + a_1 \times n^1 + a_0 \times n^0) $$ 实现
方法一： 使用进制转换
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function () {
let str = (await readline())
let hxnum = str.trim().toLowerCase().slice(2)
let decnum = 0
let base = 16
// 定义十六进制超出9以外的字符进行数字转义
const transObj = {
'a': 10,
'b': 11,
'c': 12,
'd': 13,
'e': 14,
'f': 15
}
for (let i = hxnum.length - 1; i >= 0; i--) {
// 如果本身是9以内的数字，那么直接乘以次幂
if (transObj[hxnum[i]]) {
// 本身并不是9以内的数字，那就需要转换，再乘以次幂
decnum = decnum + transObj[hxnum[i]] * (Math.pow(base, hxnum.length - 1 - i))
} else {
decnum = decnum + Number(hxnum[i]) * (Math.pow(base, hxnum.length - 1 - i))
}
}
console.log(decnum)
}()
方法二：使用 JavaScript parseInt 方法
onst readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", function (line) {
console.log(parseInt(line,16));
});
位运算基础操作
| 运算符 | 描述 | 规则 |
|---|---|---|
& | 按位与运算符 | （同1为1）只有对应的两个二进位都为 1 时，结果位才为 1 |
| ` | ` | 按位或运算符 |
<< | 左移运算符 | 将二进制数的各个二进位全部左移若干位。<< 右侧数字指定了移动位数，高位丢弃，低位补 0 |
>> | 右移运算符 | 对二进制数的各个二进位全部右移若干位。>> 右侧数字指定了移动位数，低位丢弃，高位补 0 |
^ | 按位异或运算符 | （同0异1）对应的两个二进位相异时，结果位为 1 ，二进位相同时则结果位为 0 。 |
~ | 取反运算符 | 对二进制数的每个二进位取反，使数字 1 变为 0 ，0 变为 1 |
按位与运算
按位与运算（AND）：按位与运算符为
&。其功能是对两个二进制数的每一个二进位进行与运算。
- 按位与运算规则：（ 同1为1）只有对应的两个二进位都为 1 时，结果位才为 1 。
1 & 1 = 11 & 0 = 00 & 1 = 00 & 0 = 0
举个例子，对二进制数 01111100(2) 与 00111110(2) 进行按位与运算，结果为 00111100(2) ，如图所示：
按位或运算
按位或运算（OR）：按位或运算符为
|。其功能对两个二进制数的每一个二进位进行或运算。
- 按位或运算规则：（遇1为1）只要对应的两个二进位有一个为 1 时，结果位就为 1。
1 | 1 = 11 | 0 = 10 | 1 = 10 | 0 = 0
举个例子，对二进制数 01001010(2) 与 01011011(2) 进行按位或运算，结果为 01011011(2) ，如图所示：
按位异或运算
按位异或运算（XOR）：按位异或运算符为
^。其功能是对两个二进制数的每一个二进位进行异或运算。
- 按位异或运算规则：（同0异1）对应的两个二进位相异时，结果位为 1 ，二进位相同时则结果位为 0 。
0 ^ 0 = 01 ^ 0 = 10 ^ 1 = 11 ^ 1 = 0
举个例子，对二进制数 01001010(2) 与 01000101(2) 进行按位异或运算，结果为 00001111(2) ，如图所示：
取反运算
取反运算（NOT）：取反运算符为
~。其功能是对一个二进制数的每一个二进位进行取反运算。
- 取反运算规则：使数字 1 变为 0，0 变为 1。
~0 = 1~1 = 0
举个例子，对二进制数 01101010(2) 进行取反运算，结果如图所示：
左移运算和右移运算
左移运算（SHL）： 左移运算符为
<<。其功能是对一个二进制数的各个二进位全部左移若干位（高位丢弃，低位补 00）。
举个例子，对二进制数 01101010(2) 进行左移 11 位运算，结果为 11010100(2) ，如图所示：
右移运算（SHR）： 右移运算符为
>>。其功能是对一个二进制数的各个二进位全部右移若干位（低位丢弃，高位补 00）。
举个例子，对二进制数 01101010(2) 进行右移 1 位运算，结果为 00110101(2) ，如图所示：
位运算的应用
交换两个数
通过按位异或运算可以实现交换两个数的目的（只能用于交换两个整数）。
假设 a=10,b=20，请交换 a,b 的值
a = a ^ b
b = a ^ b
a = a ^ b
结果： a=20, b=10
原理：异或运算 同 0 异 1，且满足交换率
a = a ^ b
b = a ^ b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a
a = a ^ b = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b
判断整数奇偶
一个整数：
- 只要是偶数，其对应二进制数的末尾一定为 0
- 只要是奇数，其对应二进制数的末尾一定为 1
所以，通过与 1 进行按位与运算，即可判断某个数是奇数还是偶数。（1 的二进制为 00000001，因此某数与 1 进行按位与运算，将只保留最后一位数）
(x & 1) == 0为偶数(x & 1) == 1为奇数
二进制数选取指定位
问题：从一个二进制数 𝑋 中取出某几位，使取出位置上的二进位保留原值，其余位置为 0 。
方案：可以使用另一个二进制数 𝑌 ，使该二进制数上对应取出位置为 1 ，其余位置为 0 。然后令两个数进行按位与运算（X & Y），即可得到想要的数。
原理：按位与运算（ 同1为1）都为1的位，结果为1。因此其余位与 0 按位与运算后都为 0。
示例：比如我们要取二进制数 𝑋=01101010(2) 的末尾 4 位，则只需将 𝑋=01101010(2) 与 𝑌=00001111(2) (末尾 4 位为 1 ，其余位为 0) 进行按位与运算，即 01101010 & 00001111 == 00001010。其结果 00001010 就是我们想要的数（即二进制数 01101010(2) 的末尾 4 位）。
将指定位设置为 1
问题：把一个二进制数 𝑋 中的某几位设置为 1，其余位置保留原值。
方案：可以使用另一个二进制数 𝑌 ，使得该二进制上对应选取位置为 1，其余位置为 0。然后令两个数进行按位或运算（X | Y），即可得到想要的数。
原理：按位或运算（ 遇1为1）与 1 运算的位，结果为1。因此其余位与 0 按位与运算后都保留。
示例：比如我们想要将二进制数 𝑋=01101010(2) 的末尾 4 位设置为 1 ，其余位置保留原值，则只需将 𝑋=01101010(2) 与 𝑌=00001111(2)（末尾 4 位为 1，其余位为 0 ）进行按位或运算，即 01101010 | 00001111 = 01101111。其结果 01101111 就是我们想要的数（即将二进制数 01101010(2) 的末尾 4 位设置为 1 ，其余位置保留原值）
反转指定位
问题：把一个二进制数 𝑋 的某几位进行反转。
方案：可以使用另一个二进制数 𝑌 ，使得该二进制上对应选取位置为 1 ，其余位置为 0 。然后令两个数进行按位异或运算（X ^ Y），即可得到想要的数。
原理：异或运算（同 0 异1 ）
示例：比如想要将二进制数 𝑋=01101010(2) 的末尾 4 位进行反转，则只需将 𝑋=01101010(2) 与 𝑌=00001111(2) （末尾 4 位为 1 ，其余位为 0 ）进行按位异或运算，即 01101010 ^ 00001111 = 01100101。其结果 01100101就是我们想要的数（即将二进制数 𝑋=01101010(2) 的末尾 4 位进行反转）。
将二进制最右侧为 1 的二进位改为 0
问题：将一个二进制数 𝑋 最右侧为 1 的二进制位改为 0 。
方案：只需通过 X & (X - 1) 的操作即可完成。
示例：比如 𝑋=01101100(2) ，𝑋−1=01101011(2) ，则 X & (X - 1) == 01101100 & 01101011 == 01101000，结果为 01101000(2) （即将 𝑋 最右侧第三位数为 1 的二进制为改为 0 ）
计算二进制中二进位为 1 的个数
从以上操作中得知：通过 X & (X - 1) 我们可以将二进制 𝑋 最右侧为 1 的二进制位改为 0 ，那么如果我们不断通过 X & (X - 1) 操作，最终将二进制 𝑋 变为 0 ，并统计执行次数，则可以得到二进制中二进位为 1 的个数。
function countOne(x){
let count = 0;
while(x>0) {
x = x & (x-1);
count ++
}
return count
}
求 2 的n 幂次方
方案：1 << n
原理：通过将 1 左移 n 位即 2 的 n 幂次方
判断某数是否为 2 的幂次方
方案：通过判断 X & (X - 1) == 0 是否成立，即可判断 𝑋 是否为 2 的幂次方。
原理：
- 凡是 2 的幂次方，其二进制数的某一高位为 1，并且仅此高位为 1，其余位都为 0。比如：4(10)=00000100(2) 、8(10)=00001000(2) 。
- 不是 2 的幂次方，其二进制数存在多个值为 1 的位。比如：5(10)=00000101(2) 、6(10)=00000110(2) 。
接下来使用 X & (X - 1) 操作，将原数对应二进制数最右侧为 1 的二进位改为 0 之后，得到新值：
- 如果原数是 2 的幂次方，则通过
X & (X - 1)操作之后，新值所有位都为 0 ，值为 0 。 - 如果该数不是 2 的幂次方，则通过
X & (X - 1)操作之后，新值仍存在不为 0 的位，值肯定不为 0。
所以可以通过是否为 0 即可判断该数是否为 2 的幂次方。
位运算的常用操作总结
| 功能 | 位运算 | 示例 |
|---|---|---|
| 求 2 的 n 幂次方 | 通过将 1 左移 n 位即 2 的 n 幂次方 | 2的4次方：2^4 = 800000001 << 4 = 00001000 |
| 判断整数奇偶 | 通过与 1 进行按位与运算:(x & 1) == 0 为偶数;(x & 1) == 1 为奇数 | |
| 交换两个数 | 按位异或运算 | a = a ^ bb = a ^ ba = a ^ b |
| 二进制数选取指定位 | 使用另一个二进制数 𝑌 ，使该二进制数上对应取出位置为 1 ，其余位置为 0 。 然后令两个数进行按位与运算（ X & Y） | x=01101010 , 取最后四位01101010 & 00001111 == 00001010 |
| 将指定位设置为 1 | 使用另一个二进制数 𝑌 ，使得该二进制上对应选取位置为 1，其余位置为 0。 然后令两个数进行按位或运算（`X | Y`） |
| 反转指定位 | 使用另一个二进制数 𝑌 ，使得该二进制上对应选取位置为 1 ，其余位置为 0 。 然后令两个数进行按位异或运算（ X ^ Y） | 𝑋=01101010(2) 的末尾 4 位进行反转01101010 ^ 00001111 = 01100101 |
| 将二进制最右侧为 1 的二进位改为 0 | X & (X - 1) | 𝑋=01101100 X & (X - 1) == 01101100 & 01101011 == 01101000 |
| 判断某数是否为 2 的幂次方 | 判断 X & (X - 1) == 0 是否成立 | |
| 从右边开始，把最后一个 1 改写成 0 | x & (x - 1) | 100101000 -> 100100000 |
| 去掉右边起第一个 1 的左边 | x & (x ^ (x - 1)) 或 x & (-x) | 100101000 -> 1000 |
| 去掉最后一位 | x >> 1 | 101101 -> 10110 |
| 取右数第k 位 | x >> (k - 1) & 1 | 1101101 -> 1, k = 4 |
| 取末尾 3 位 | x & 7 | 1101101 -> 101 |
| 取末尾 𝑘 位 | x & 15 | 1101101 -> 1101, k = 4 |
| 只保留右边连续的 1 | (x ^ (x + 1)) >> 1 | 100101111 -> 1111 |
| 右数第 𝑘 位取反 | x ^ (1 << (k - 1)) | 101001 -> 101101, k = 3 |
| 在最后加一个 0 | x << 1 | 101101 -> 1011010 |
| 在最后加一个 1 | (x << 1) + 1 | 101101 -> 1011011 |
| 把右数第 𝑘位变成 0 | x & ~(1 << (k - 1)) | 101101 -> 101001, k = 3 |
| 把右数第 𝑘 位变成 1 | `x | (1 << (k - 1))` |
| **把右边起第一个 0 变成 1 ** | `x | (x + 1)` |
| 把右边连续的 0 变成 1 | `x | (x - 1)` |
| 把右边连续的 1 变成 0 | x & (x + 1) | 100101111 -> 100100000 |
| **把最后一位变成 0 ** | `x | 1 - 1` |
| 把最后一位变成 1 | `x | 1` |
| 把末尾 𝑘位变成 1 | `x | (1 << k - 1)` |
| 最后一位取反 | x ^ 1 | 101101 -> 101100 |
| 末尾 𝑘 位取反 | x ^ (1 << k - 1) | 101001 -> 100110, k = 4 |
二进制枚举子集
问题：给定一个集合 𝑆S，枚举其所有可能的子集。
方案：对于一个元素个数为 n 的集合 𝑆 来说，每一个位置上的元素都有选取和未选取两种状态。我们可以用数字 1 来表示选取该元素，用数字 0 来表示不选取该元素。
那么我们就可以用一个长度为 𝑛 的二进制数来表示集合 𝑆 或者表示 𝑆 的子集。其中二进制的每一个二进位都对应了集合中某一个元素的选取状态。对于集合中第 𝑖 个元素来说，二进制对应位置上的 1 代表该元素被选取，0 代表该元素未被选取。
示例：比如长度为 5 的集合 𝑆={5,4,3,2,1} ，我们可以用一个长度为 5 的二进制数来表示该集合：
- 二进制数 11111(2) 就表示选取集合的第 1 位、第 2 位、第 3 位、第 4 位、第 5 位元素，也就是集合 {5,4,3,2,1} ，即集合 𝑆 本身。
- 二进制数 10101(2) 就表示选取集合的第 1 位、第 3 位、第 5 位元素，也就是集合 {5,3,1} 。
- 二进制数 01001(2) 就表示选取集合的第 1 位、第 4 位元素，也就是集合 {4,1} 。
结论：对于长度为 𝑛 的集合 𝑆 ，只需要枚举 0∼2^𝑛−1 （共 2^𝑛 种情况），即可得到集合 S 的所有子集。
function subsets(S) {
const n = S.length; // n 为集合 S 的元素个数
const subSets = []; // subSets 用于保存所有子集
// 枚举 0 ~ 2^n - 1
for (let i = 0; i < (1 << n); i++) {
const subSet = []; // subSet 用于保存当前子集
// 枚举第 i 位元素
for (let j = 0; j < n; j++) {
// 如果第 i 位元素对应二进位为 1，则表示选取该元素
if ((i >> j) & 1) {
subSet.push(S[j]); // 将选取的元素加入到子集 subSet 中
}
}
subSets.push(subSet); // 将子集 subSet 加入到所有子集数组 subSets 中
}
return subSets; // 返回所有子集
}
算法题
| 题号 | 标题 | 标签 | 难度 |
|---|---|---|---|
| 0504 | 七进制数 | 数学 | 简单 |
| 0405 | 数字转换为十六进制数 | 位运算、数学 | 简单 |
| 0190 | 颠倒二进制位 | 位运算、分治 | 简单 |
| 1009 | 十进制整数的反码 | 位运算 | 简单 |
| 0191 | 位1的个数 | 位运算、分治 | 简单 |
| 0371 | 两整数之和 | 位运算、数学 | 中等 |
| 0089 | 格雷编码 | 位运算、数学、回溯 | 中等 |
| 0201 | 数字范围按位与 | 位运算 | 中等 |
| 0338 | 比特位计数 | 位运算、动态规划 | 简单 |
| 0136 | 只出现一次的数字 | 位运算、数组 | 简单 |
| 0137 | 只出现一次的数字 II | 位运算、数组 | 中等 |
| 0260 | 只出现一次的数字 III | 位运算、数组 | 中等 |
| 0268 | 丢失的数字 | 位运算、数组、哈希表、数学、二分查找、排序 | 简单 |
| 1349 | 参加考试的最大学生数 | 位运算、数组、动态规划、状态压缩、矩阵 | 困难 |
| 0645 | 错误的集合 | 位运算、数组、哈希表、排序 | 简单 |
| 0078 | 子集 | 位运算、数组、回溯 | 中等 |
| 0090 | 子集 II | 位运算、数组、回溯 | 中等 |
七进制数
题目
给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。
示例 1:
输入: num = 100
输出: "202"
示例 2:
输入: num = -7
输出: "-10"
解法：除 7 取余法
function convertToBase7(num: number): string {
if (num === 0) return '0'
let result: Array<string> = []
let digist = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
let isNagative = num < 0
num = Math.abs(num)
while (num > 0) {
let remider = num % 7
result.push(digist[remider])
num = Math.floor(num / 7)
}
if (isNagative) {
result.push('-')
}
return result.reverse().join('')
};
数字转换为十六进制数
题目
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
- 十六进制中所有字母(
a-f)都必须是小写。 - 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符
'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。 - 给定的数确保在32位有符号整数范围内。
- 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
示例 1：
输入:
26
输出:
"1a"
示例 2：
输入:
-1
输出:
"ffffffff"
解法一：位运算 + 分组换算
题目要求将给定的整数 num 转换为十六进制数，负整数使用补码运算方法。
在补码运算中：
- 最高位表示符号位，符号位是 0 表示正整数和零，符号位是 1 表示负整数。
32位有符号整数的二进制数有 32 位，由于一位十六进制数对应四位二进制数，因此 32 位有符号整数的十六进制数有 8 位。将 num 的二进制数按照四位一组分成 8 组，依次将每一组转换为对应的十六进制数，即可得到 num 的十六进制数。
假设二进制数的 8 组从低位到高位依次是第 0 组到第 7 组，则对于第 i 组，可以通过 (nums>>(4×i)) & 0xf 得到该组的值，其取值范围是 0 到 15 （即十六进制的 f ）。
将每一组的值转换为十六进制数的做法如下：
- 对于 0 到 9 ，数字本身就是十六进制数；
- 对于 10 到 15 ，将其转换为 a 到 f 中的对应字母。
对于负整数，由于最高位一定不是 0 ，因此不会出现前导零。对于零和正整数，可能出现前导零。避免前导零的做法如下：
- 如果 num=0 ，则直接返回 0 ；
- 如果 num>0 ，则在遍历每一组的值时，从第一个不是 0 的值开始拼接成十六进制数。
var toHex = function(num) {
// 如果输入的数是0，直接返回字符串"0"
if (num === 0) {
return "0";
}
// 创建一个空数组，用于存储转换后的十六进制字符
const sb = [];
// 从最高位（32位中的第8个4位组，因为每个十六进制字符表示4位）开始遍历
// 注意，由于JavaScript的位操作符限制在32位，所以我们只需要遍历到第0个4位组
for (let i = 7; i >= 0; i --) {
// 使用无符号右移（>>>）运算符将当前4位组移动到最低位
// 然后与0xf（即15，二进制为1111）进行与运算，得到当前4位组的值（0-15）
const val = (num >>> (4 * i)) & 0xf;
// 如果sb数组已经有内容，或者当前4位组的值不为0（即不是前导零）
// 则将当前4位组的值转换为对应的十六进制字符，并添加到sb数组中
if (sb.length > 0 || val > 0) {
// 如果val的值小于10（即0-9），则转换为对应的字符'0'-'9'
// 否则，转换为对应的字符'a'-'f'
const digit = val < 10 ? String.fromCharCode('0'.charCodeAt() + val) : String.fromCharCode('a'.charCodeAt() + val - 10);
sb.push(digit);
}
}
// 将sb数组中的字符连接成一个字符串，并返回
return sb.join('');
}
解法二
将长度为 32 的二进制转换为 16 进制数，本质是对长度为 32 的二进制数进行分组，每 4 个一组，二进制 1111(2) 表示 15 ，则使用长度为 4 的二进制可以表示 (0-15）。
同时，由于我们是直接对长度为 32 的二进制进行分组转算（4 个为一组，共 8 组），而长度为 32 的二进制本身就是使用补码规则来表示的，因此我们无须额外处理「补码」问题。
具体的，我们将 num 与 15 = 1111(2) 进行 & 运算，然后对 num 进行无符号右移 4 位来实现每 4 位处理。
function toHex(num: number): string {
// 十六进制字符的字符串表示
const hexChars = "0123456789abcdef";
// 如果整数为0，直接返回"0"
if (num === 0) return "0";
// 如果需要处理负数，我们可以将其转换为正数，但在这个情况下，由于位运算符限制在 32 位，
// 我们实际上只需要将负数视为无符号的 32 位整数（即，在数值上加上 2^32）
let unsignedNum = num;
// 如果输入是负数，我们需要将其转换为无符号的 32 位整数（即，在数值上加上 2^32）
if (num < 0) {
unsignedNum = num + Math.pow(2, 32);
}
let ans = ''; // 使用空字符串来收集十六进制字符
// 循环直到 unsignedNum 为 0
while (unsignedNum > 0) {
// 取出 unsignedNum 的最低 4 位（即一个十六进制位）
const temp = unsignedNum & 15; // 使用位与运算符取出最后 4 位
// 将这 4 位转换为对应的十六进制字符
ans = hexChars[temp] + ans; // 将这个十六进制字符添加到结果字符串的开头
// 使用无符号右移 4 位来移除已经处理过的 4 位
unsignedNum >>>= 4; // 注意这里使用无符号右移，因为我们处理的是无符号整数
}
// 返回结果字符串
return ans;
};