最近在leetcode刷题,发现了一道很有意思的题

258. 各位相加

给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

示例:

输入: 38
输出: 2 
解释: 各位相加的过程为:3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数,所以返回 2。

进阶:
你可以不使用循环或者递归,且在 O(1) 时间复杂度内解决这个问题吗?

乍一看,有点没有头绪,但是计算机导论的知识告诉我这个东西与二进制有关。

 

然后我翻了翻大佬的解法,瞬间就被骚到了。

1 class Solution {
2     public int getSum(int a, int b) {
3         return b == 0 ? a : getSum(a^b,(a&b)<<1); 
4     }
5 }

一行解,而且快到令人发指。

 关于竞赛中位运算的用法 算法

 

原理:两个整数a, b; a ^ b是无进位的相加; a&b得到每一位的进位;让无进位相加的结果与进位不断的异或, 直到进位为0;

 

底下这篇文章是详解位运算:

https://blog.csdn.net/goskalrie/article/details/52796360

我将这篇文章总结了一下,针对竞赛方面:

1. 位运算符

1.1 java支持的位运算符:

&:按位与。

|:按位或。

~:按位非。

^:按位异或。

<<:左位移运算符。

>>:右位移运算符。

>>>:无符号右移运算符。(原文章这个位置错了)

左和右位移运算符:

<<  :  比如 5<<7 = 5*2^7

>> :   比如 5>>7=5/2^7

^ :   比如 a ^ b是无进位的相加

&  :    比如a&b得到每一位的进位

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄