题解 | #求1+2+3+...+n#

求1+2+3+...+n

https://www.nowcoder.com/practice/7a0da8fc483247ff8800059e12d7caf1

基本思路:

  • 高斯公式n * (n + 1) / 2
  • 只能用加减、位操作、逻辑,所以用快速乘来实现n * (n + 1)
  • 快速乘需要一次判断,当最低位为0时才相加,考虑用短路操作实现判断逻辑。
  • n最大也只有200,换算成二进制也就是9位,所以把循环展开9次就行了(实际上8次就够了)
class Solution {
public:
    int Sum_Solution(int n) {
        int m = n + 1, res = 0;
        (m & 1) && (res += n);
        n += n;
        m >>= 1;
        (m & 1) && (res += n);
        n += n;
        m >>= 1;
        (m & 1) && (res += n);
        n += n;
        m >>= 1;
        (m & 1) && (res += n);
        n += n;
        m >>= 1;
        (m & 1) && (res += n);
        n += n;
        m >>= 1;
        (m & 1) && (res += n);
        n += n;
        m >>= 1;
        (m & 1) && (res += n);
        n += n;
        m >>= 1;
        (m & 1) && (res += n);
        n += n;
        m >>= 1;
        return res >> 1;
    }
};

全部评论

相关推荐

码农索隆:想看offer细节
点赞 评论 收藏
分享
深夜书店vv:腾讯是这样的,去年很多走廊都加桌子当工区
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 16:22
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务