涉及到位运算的数据结构与算法题。

题目一

该题很容易出现在各大厂的面试中，属于必须掌握的题型。

题目描述：

求 1 至 n 连续 n 个数的和。要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C）。
1 <= n <= 10000

解法一：
直接等差求和公式显然不行，因为包含乘除法。不行。吗？逻辑右移搞定！

代码：

// 套公式加位运算
function sumF(n) {
    return (Math.pow(n, 2) + n) >>> 1;  // 无符号右移，不过这里有没有符号都一样，因为 n 是正整数
}

解法二：

递归要有终止条件，需要 if 判断，也不行。吗？可以使用逻辑判断运算符绕过！嘻嘻

为了对比，先写一个无限制的递归版吧：

// 正常递归版
function sumN(n) {
    if (n <= 0) {
        return 0;
    }
    return n + sumN(n - 1);
}

使用逻辑或运算：

// 使用逻辑运算
function sumH(n) {
    return n > 0 && (n + (sumH(n - 1)));
}

这里利用了 JavaScript 逻辑运算的特殊性。即逻辑运算返回值保持表达式原值！

题目二

给定一个整数 n，编写一个函数来判断它是否是 2 的幂次方。
$-2^{31} <= n <= 2^{31} - 1$
进阶：你能够不使用循环 / 递归解决此问题吗？

解法一：
利用位运算中的按位或运算。2 的幂都是首 1 全 0 的二进制。
while 循环加位运算：

function is2(n) {
    if (n <= 0) {
        return false;
    }
    while (true) {
        if (n === 1) {
            return true;
        }
        if (n & 1 === 1) {
            // 说明 n 的二进制表示中最后一个二进制位是 1
            return false;
        }
        n = n >>> 1;
    }
}

解法二：
利用 2 的幂的二进制，减去一，是全 1 的二进制。

var isPowerOfTwo = function(n) {
    return n > 0 && (n & (n-1)) === 0;
};

参考

• 和小浩学算法. pdf