/** * bit相关工具类 */ bitUtils = { /** * @description 此方法将相关位移到第0位。执行与操作，如果相关位为1，则结果为1，否则结果为0。 * @param {number} number * @param {number} bitPosition - zero based. * @return {number} */ getBit: function(number, bitPosition) { return (number >> bitPosition) & 1; }, /** * @description 此方法按位置位移动1，执行或操作，将特定位设置为1，但不影响数字的其他位。 * @param {number} number * @param {number} bitPosition - zero based. * @return {number} */ setBit: function(number, bitPosition) { return number | (1 << bitPosition); }, /** * @description 此方法按位位置位移动1，创建一个类似于00100的值。然后它反转这个掩码，得到看起来像11011的数字。然后，操作将同时应用于数字和掩码。那次操作使钻头复位。 * @param {number} number * @param {number} bitPosition - zero based. * @return {number} */ clearBit: function(number, bitPosition) { const mask = ~ (1 << bitPosition); return number & mask; }, /** * @description 此方法为setBit与clearBit的结合，更新指定为的值 * @param {number} number * @param {number} bitPosition - zero based. * @param {number} bitValue - 0 or 1. * @return {number} */ updateBit: function(number, bitPosition, bitValue) { const bitValueNormalized = bitValue ? 1 : 0; const clearMask = ~ (1 << bitPosition); return (number & clearMask) | (bitValueNormalized << bitPosition); }, /** * @description 此方法确定提供的数字是否为偶数。这是基于奇数的最后一个正确位被设置为1的事实。 * @param {number} number * @return {boolean} */ isEven: function(number) { return (number & 1) === 0; }, /** * @description 此方法确定数字是否为正。它基于这样一个事实：所有正数的最左边的位都设置为0。但是，如果提供的数字为零或负零，则仍应返回false。 * @param {number} number * @return {boolean} */ isPositive: function(number) { if (number === 0) { return false; } return ((number >> 31) & 1) === 0; }, /** * @description 此方法将原始数字向左移动一位。因此，所有二进制数的分量（2的幂）都是乘2的，因此数字本身是乘2的。 * @param {number} number * @return {number} */ multiplyByTwo: function(number) { return number << 1; }, /** * @description 此方法将原始数字向右移动一位。因此，所有二进制数的分量（2的幂）都被2除，因此数字本身被2除，没有余数。 * @param {number} number * @return {number} */ divideByTwo: function(number) { return number >> 1; }, /** * @description 这种方法使正数变成负数和倒数。为了做到这一点，它使用了“两个补码”的方法，通过反转数字的所有位并加上1来实现。 * @param {number} number * @return {number} */ switchSign: function(number) { return~ number + 1; }, /** * @description 此方法使用位运算符将两个有符号整数相乘。该方法基于以下事实： a*b可以用以下格式书写： 0如果a为零或b为零或a和b都为零 2a*（b/2）如果b是偶数 2a*（b-1）/2+a如果b是奇数正的 2a*（b+1）/2-a如果b是奇数和负数 这种方法的优点是，在每个递归步骤中，一个操作数减少到其原始值的一半。因此，运行时复杂度是O（log（b）），其中B是在每个递归步骤上减少到一半的操作数。 * @param {number} number * @return {number} */ multiply: function(a, b) { if (b === 0 || a === 0) { return 0; } const multiplyByOddPositive = () = > this.multiply(this.multiplyByTwo(a), this.divideByTwo(b - 1)) + a; const multiplyByOddNegative = () = > this.multiply(this.multiplyByTwo(a), this.divideByTwo(b + 1)) - a; const multiplyByEven = () = > this.multiply(this.multiplyByTwo(a), this.divideByTwo(b)); const multiplyByOdd = () = > (this.isPositive(b) ? multiplyByOddPositive() : multiplyByOddNegative()); return this.isEven(b) ? multiplyByEven() : multiplyByOdd(); }, /** * @description 此方法使用位运算符将两个整数相乘。这种方法是基于“每个数都可以表示为2的幂和”。按位乘法的主要思想是，每一个数可以被分成两个幂的和： 即。19=2^4+2^1+2^0,那么x乘以19等于：x*19=x*2^4+x*2^1+x*2^0。现在我们需要记住，x*2^4相当于将x左移4位（x<4）。 * @param {number} number1 * @param {number} number2 * @return {number} */ multiplyUnsigned: function(number1, number2) { let result = 0; let multiplier = number2; let bitIndex = 0; while (multiplier !== 0) { if (multiplier & 1) { result += (number1 << bitIndex); } bitIndex += 1; multiplier >>= 1; } return result; }, /** * @description 此方法使用按位运算符计算数字中的设置位数。主要思想是，我们一次将数字右移一位，然后检查&operation的结果，如果设置了位，则结果为1，否则结果为0。 * @param {number} originalNumber * @return {number} */ countSetBits: function(originalNumber) { let setBitsCount = 0; let number = originalNumber; while (number) { setBitsCount += number & 1; number >>= 1; } return setBitsCount; }, /** * @description 此方法输出将一个数转换为另一个数所需的位数。这利用了这样一个特性：当数字被异或时，结果将是不同位的数字。 * @param {number} numberA * @param {number} numberB * @return {number} */ bitsDiff: function(numberA, numberB) { return this.countSetBits(numberA ^ numberB); }, /** * @description 为了计算有价值的位数，我们需要每次左移1位，看看移位的位数是否大于输入位数。 * @param {number} number * @return {number} */ bitLength: function(number) { let bitsCounter = 0; while ((1 << bitsCounter) <= number) { bitsCounter += 1; } return bitsCounter; }, /** * @description 此方法检查提供的数字是否为2的幂。它使用以下属性。假设power number是一个由2的幂（即2、4、8、16等）构成的数。然后如果我们在power number和powerNumber-1之间执行操作，它将返回0（如果number是2的幂）。 * @param {number} number * @return {boolean} */ isPowerOfTwo: function(number) { return (number & (number - 1)) === 0; }, /** * @description 此方法使用按位运算符将两个整数相加。 * * Table(1) * INPUT | OUT * C Ai Bi | C Si | Row * -------- | -----| --- * 0 0 0 | 0 0 | 1 * 0 0 1 | 0 1 | 2 * 0 1 0 | 0 1 | 3 * 0 1 1 | 1 0 | 4 * -------- | ---- | -- * 1 0 0 | 0 1 | 5 * 1 0 1 | 1 0 | 6 * 1 1 0 | 1 0 | 7 * 1 1 1 | 1 1 | 8 * --------------------- * * Legend: * INPUT C = Carry in, from the previous less-significant stage * INPUT Ai = ith bit of Number A * INPUT Bi = ith bit of Number B * OUT C = Carry out to the next most-significant stage * OUT Si = Bit Sum, ith least significant bit of the result * * @param {number} a * @param {number} b * @return {number} */ fullAdder: function(a, b) { let result = 0; let carry = 0; for (let i = 0; i < 32; i += 1) { const ai = this.getBit(a, i); const bi = this.getBit(b, i); const carryIn = carry; const aiPlusBi = ai ^ bi; const bitSum = aiPlusBi ^ carryIn; const carryOut = (aiPlusBi & carryIn) | (ai & bi); carry = carryOut; result |= bitSum << i; } return result; } }