[LeetCode] Divide Two Integers
LeetCode two Integers
2023-09-11 14:17:25 时间
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
思路:用 divisor 右移,计算出最大的位数,然后不断比较 更新过的dividend 和 divisor << number, 直到number =0;
Note:1 abs()的原型是abs(int),所以abs(long long int) 会溢出,不能使用,可以使用llabs,我这里直接自己计算了。
#include <stdlib.h>
int abs(int j);
long int labs(long int j);
long long int llabs(long long int j);
2 在移位操作中, 不能直接使用1<< num, 要使用1ULL, 如果不写UL后缀,系统默认为:int, 即,有符号整数,如果移位超过32位,将发生溢出。
另外,在32bits系统中,long移位32为, 所以为了保证不溢出,要使用64bits 的long long 类型。
cout << (1 << 31) << endl; cout << (1u << 31) << endl; cout << (1 << 32) << endl; cout << (1ull << 32) << endl;
结果为:
-2147483648 2147483648 0 4294967296
1 为int, 1u 为unsigned int, 1 << 32, 溢出,结果为0, 1ull <<32未溢出。
class Solution { public: int divide(int dividend, int divisor) { int leftShiftBits= 0; long long divd = dividend; long long divr = divisor; long long result = 0; int sign = 1; if( (divd < 0 && divr > 0) || (divd > 0 && divr < 0) ) sign = -1; # if 0 //note abs(int) can't handle abs(long), so abs(INT_MIN) will overflow divd = abs(divd); divr = abs(divr); # endif if(divd < 0) divd = -divd; if(divr < 0) divr = -divr; while( (divr << leftShiftBits) < divd) { leftShiftBits ++; } //leftShiftBits --; //the function can work with or without this scentence while(leftShiftBits >= 0) { if(divd >= (divr << leftShiftBits)) { result += 1ULL << leftShiftBits; divd -= (divr << leftShiftBits); } leftShiftBits --; } if((result * sign) > INT_MAX) return INT_MAX; else if((result * sign) < INT_MIN) return INT_MIN; return result * sign; } };
相关文章
- Leetcode: Maximum XOR of Two Numbers in an Array
- Leetcode: Intersection of Two Arrays
- Leetcode: Wildcard Matching
- Leetcode: Path Sum
- LeetCode高频题128. 最长连续序列,经常被互联网大厂面试考到
- [LeetCode] Word Ladder II
- 183、【动态规划】leetcode ——516. 最长回文子序列(C++版本)
- 【LeetCode】338. Counting Bits (2 solutions)
- 【LeetCode】4. Median of Two Sorted Arrays (2 solutions)
- 【LeetCode】46. Permutations (2 solutions)
- 【LeetCode】21. Merge Two Sorted Lists
- 【LeetCode】111. Minimum Depth of Binary Tree (2 solutions)
- 【LeetCode】1. Two Sum
- [leetcode]Pascal's Triangle
- [LeetCode] 1312. Minimum Insertion Steps to Make a String Palindrome 让字符串成为回文串的最少插入次数
- [LeetCode] 1029. Two City Scheduling 两个城市调度
- [LeetCode] Rabbits in Forest 森林里的兔子
- [LeetCode] Split Linked List in Parts 拆分链表成部分
- [LeetCode] Minimum ASCII Delete Sum for Two Strings 两个字符串的最小ASCII删除和
- [LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树
- [LeetCode] Construct String from Binary Tree 根据二叉树创建字符串
- [LeetCode] Minimum Index Sum of Two Lists 两个表单的最小坐标和
- [LeetCode] 421. Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字
- [LeetCode] 29. Divide Two Integers 两数相除
- [LeetCode] 160. Intersection of Two Linked Lists 求两个链表的交点
- Leetcode——2. Add Two Numbers