bitUtils详解编程语言

/** 
* 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; 
} 
}