leetcodeブラシ-面接問題64.1+2+...+nを求めます

面接問題1+2+...+nを求めます
1+2+…+nを求めて、乗除法、for、while、if、else、switch、caseなどのキーワードと条件の判断文(A?B:C)を使うことができないことを要求します.

   1：

  : n = 3
  : 6

制限:

1 <= n <= 10000

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/qiu-12n-lcof考え方:方法1:加減法を使用し、サイクルを使用できず、再帰を使用する.関数は、1--nまたはn--1の順に戻り、加算されます.考えやすいのですが、

class Solution {
public:
    int sumNums(int n) {
		return n==0?n:n+=sumNums(n-1):
    }
};

n=0の場合は終了条件となりますが、タイトルでは条件判定文は使用できません.すなわち、別の文で判断する必要があります.判断の性質を持つものには論理演算子がありますが、そのうちA&&B、AがFALSEであれば、Bは行われません.コードは次のようになります.

class Solution {
public:
    int sumNums(int n) {
		return n&&n+=sumNums(n-1):
    }
};

方法2:数学の方法によって、1+2+…+n等しいn*(n+1)、乗算の中でビット演算を使ってどのように表しますか?例えばA×B、Bバイナリ表示では1の位のみが乗算に貢献し、第i位は1、すなわち対A左シフトi位、例えば1×3、3のバイナリ表示は0011、第0位は1、第1位は1、それぞれ左シフトは0位、1位は1、2、最終結果は1+2=3なのでn*(n+1)のはn+1のは1の位でnを左にシフトして加算することができます.快速乗と呼ぶ.

int quickMulti(int A, int B) {
    int ans = 0;
    for ( ; B; B >>= 1) {
        if (B & 1) {
            ans += A;
        }
        A <<= 1;
    }
    return ans;
}

ループは使用できないため、手動で展開するしかありません.nは最大10000で、バイナリは最大14ビット表示が必要です.

class Solution {
public:
    int sumNums(int n) {
        int ans = 0, A = n, B = n + 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        (B & 1) && (ans += A);
        A <<= 1;
        B >>= 1;

        return ans >> 1;

    }
};