Sum of Two Integers
2018-06-17 23:49:59来源:未知 阅读 ()
Calculate the sum of two integers a and b, but you are not allowed to use the operator +
and -
.
Example:
Given a = 1 and b = 2, return 3.
个人思路:绕开+、-,利用循环和 += 与 -= 。
class Solution { public: int getSum(int a, int b) { double x = a, y = b; double c = fabs(y); for (double i = 1; i <= c; i++) { if (b > 0) a++; if (b < 0) a--; } return a; } };
错误原因:特殊值的计算。a = 2147483647, b = -2147483647。Time Limit Exceeded
自己在电脑上跑结果是对的,然而循环次数太多了,浪费时间,比较笨的一种方法,年轻人,还是太傻太天真,还需要学习一个。
其他思路:
1.利用下标偏移自带加法 by dimle
int getSum(int a, int b) { auto c = (char*)(a); return (int)((int64_t)(&c[b])); }
把a变成一个地址为a的指针c,把它看成数组,偏移b后,地址变成a + b,再把地址转成int。(补充学习:<inttypes.h>)
2.利用位运算 by vdvvdd
class Solution { public: int getSum(int a, int b) { int sum = a; while (b != 0) { sum = a ^ b;//calculate sum of a and b without thinking the carry b = (a & b) << 1;//calculate the carry a = sum;//add sum(without carry) and carry } return sum; } };
解释:
class Solution { public: int getSum(int a, int b) { // Take 1 + 2 for example in 4 bits. // Same as 0001 + 0010 // Binary addition requires going through each bit position and // generating a carry in bit, carry out bit and sum bit. // For example, in bit position 0 in 0001 + 0010, // carry in: 0, sum bit: carry in + 1 + 0 = 1, carry out: 0 // For bit position 1, // carry in: 0, sum bit: carry in + 0 + 1 = 1, carry out: 0 // Using a truth table, we can figure out that // sum bit = carry in xor bit_a xor bit_b. // carry out = (carry in AND bit_a) OR (carry in AND bit_b) OR (bit_a AND bit_b) // carry out becomes the carry in for the next bit position. int result = 0x0; int sum_bit = 0x0; int carry_bit = 0x0; int bitmask = 0x1; int bit_a = 0x0; int bit_b = 0x0; int i = 0; // Keep track of what bit position im in. while (bitmask != 0x0) { // Isolate bits in each bit position. bit_a = (a & bitmask) >> i; bit_b = (b & bitmask) >> i; // Calculate sum, carry_bit is a carry in now. sum_bit = ((carry_bit ^ bit_a) ^ bit_b); // Shift sum_bit to correct bit position, OR into result. result |= (sum_bit << i); // Calculate carry out, carry_bit is now a carry out after calculation. carry_bit = ((bit_a & bit_b) | (carry_bit & bit_a)) | (carry_bit & bit_b); // Shift bitmask over 1 to the left. bitmask <<= 1; // Increment bit position. ++i; } return result; } };
3. 另一种位运算 by cjchan0210
class Solution { public: int getSum(int a, int b) { if(a && b) return getSum(a^b, (a&b) << 1); else return a|b; } }; viewed as binary, c = (a&b)<<1 means carry bits, and d = a^b means sum without carry obviously... and then get the sum of c and d... if a or b is 0, return a or b, so that is a|b
拓展阅读:https://discuss.leetcode.com/topic/50315/a-summary-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- CodeForces 710D Two Arithmetic Progressions 2020-03-06
- Max Sum 2020-02-17
- bzoj3944 Sum 2019-12-25
- Ural 1248 Sequence Sum 题解 2019-08-16
- DP_Sumsets 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash