SetBit [位操作]

# 介绍

什么是 set bit？一个数字的二进制表示由 0 和 1 组成，这里，1 被称为 set bit。

什么是 mask bit？mask 定义了你想保留哪些位，以及你想清除哪些位。所以，masking 是对一个值应用 masK 的行为。

# 位运算

与 & ：两位同时为 “1”，结果才为 “1”，否则为 0。
或 | ：两位其中一个为 “1”，结果为 “1”，否则为 0。
非 ~ ：单目运算符。

无符号整数：
  二进制原码：0000 0000 0000 0000 0000 0000 0000 0101
  取反操作后：1111 1111 1111 1111 1111 1111 1111 1010
有符号整数都是用补码来表示，而补码=反码+1。
  先求反码：1000 0000 0000 0000 0000 0000 0000 0101
  再求补码：1000 0000 0000 0000 0000 0000 0000 0110
  最高位代表符号位 1 表示负数，0 表示正数。

1
2
3
4
5
6
7

异或 ^ ：两位不同，结果为 “1”，否则为 0。
左移位 << ：将数值向左移动 1 位，用 0 补足。
右移位 >> ：将数值向右移动 1 位。

# 实现

# JavaScript

给定一个数字 N，任务是置位这个数字 N 的第 K 位。如果第 K 位是 0，则置位为 1，如果是 1 则保持不变。

/*
 * Setting Bit: https://www.geeksforgeeks.org/set-k-th-bit-given-number/
 *
 * To set any bit we use bitwise OR (|) operator.
 *
 * Bitwise OR (|) compares the bits of the 32
 * bit binary representations of the number and
 * returns a number after comparing each bit.
 *
 * 0 | 0 -> 0
 * 0 | 1 -> 1
 * 1 | 0 -> 1
 * 1 | 1 -> 1
 *
 * In-order to set kth bit of a number (where k is the position where bit is to be changed)
 * we need to shift 1 k times to its left and then perform bitwise OR operation with the
 * number and result of left shift performed just before.
 *
 * References:
 * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_OR
 */

/**
 * @param {number} n
 * @param {number} k - zero based.
 * @return {number}
 */

export const setBit = (n, k) => {
  return n | (1 << k)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 扩展

clear K-th bit of a number N：

给定一个数字 N，任务是清除这个数字 N 的第 K 位。如果第 K 位是 1，则清除为 0，如果是 0 则保持不变。

// JavaScript program to clear K-th bit of a number N
 
// Function to clear the kth bit of n
function clearBit(n, k)
{
    return (n & (~(1 << (k - 1))));
}

1
2
3
4
5
6
7

在一个给定的位置修改一个位：

给定一个数字 n，一个位置 p 和一个二进制值 b，我们需要将 n 中位置 p 的比特改为 b 值。

// Javascript program to modify a bit
// at position p in n to b.
// see https://www.geeksforgeeks.org/modify-bit-given-position/
 
// Returns modified n.
function modifyBit(n, p, b)
{
    let mask = 1 << p;
    return (n & ~mask) |
           ((b << p) & mask);
}

1
2
3
4
5
6
7
8
9
10
11

# 参考

编辑

上次更新: 2022/10/22, 22:03:41

← PowerOfTwo [2的幂] AllCombinationsOfSizeK [全组合]→