由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - 问个题1：implement + - * / without arithmetic operation
相关主题
● 请教一道面试题,关于tree的● one C++ question
● amazon的那道题目● 发个题目给大家复习一下marco
● Interview questions, Bloomberg● Why I can't compile this function successfully
● 一个容易记忆的permutation算法● C++: what is the output? How to interpret it?
● 好记(但不是最优)的combination算法● C++ Q42: (C22)
● one C++ question● 问个c++题
● C++ object size一问● C++问题
● One C++ question● 弱问个C++ 问题 （const_cast）
相关话题的讨论汇总
话题: int话题: add话题: div话题: mul话题: result
进入JobHunting版参与讨论
1 (共1页)
w*******s
发帖数: 96
1
How to implement + - * / without arithmetic operation?
e***s
发帖数: 799
2
int add(int x, int y) {
int carry = 0;
int result = 0;
int i;
for(i = 0; i < 32; ++i) {
int a = (x >> i) & 1;
int b = (y >> i) & 1;
result |= ((a ^ b) ^ carry) << i;
carry = (a & b) | (b & carry) | (carry & a);
}
return result;
}
f********e
发帖数: 166
3
赞楼上的代码!
y*******g
发帖数: 6599
4
++i不算arithmetic？

【在 e***s 的大作中提到】
: int add(int x, int y) {
: int carry = 0;
: int result = 0;
: int i;
: for(i = 0; i < 32; ++i) {
: int a = (x >> i) & 1;
: int b = (y >> i) & 1;
: result |= ((a ^ b) ^ carry) << i;
: carry = (a & b) | (b & carry) | (carry & a);
: }
f********e
发帖数: 166
5
照葫芦画瓢实现了个减法,调用加法，我觉得++不算算术运算符吧，除了+,-.*,/吧
int substract(int x, int y) {
int carry = 0;
int result = 0;
int t = ~y;
t = add(t,1); //t 是y 的相反数
for(int i = 0; i < 32; ++i) {
int a = (x >> i) & 1;
int b = (t >> i) & 1;
result |= ((a ^ b) ^ carry) << i;
carry = (a & b) | (b & carry) | (carry & a);
}
return result;
}
u**r
发帖数: 663
6
++i不算的话，你int x +　int y直接用++x循环就完了。
c****p
发帖数: 6474
7
慢。
O(n) VS O(logn)的区别。

【在 u**r 的大作中提到】
: ++i不算的话，你int x +　int y直接用++x循环就完了。
g*****i
发帖数: 2162
8
这个复杂度偏高,careercup上有更快的,类似这样吧:
result=x^y;
carry=(x&y)<<1;
while(carry != 0){
temp=result^carry;
carry=(result&carry)<<1;
result=temp;
}

【在 e***s 的大作中提到】
: int add(int x, int y) {
: int carry = 0;
: int result = 0;
: int i;
: for(i = 0; i < 32; ++i) {
: int a = (x >> i) & 1;
: int b = (y >> i) & 1;
: result |= ((a ^ b) ^ carry) << i;
: carry = (a & b) | (b & carry) | (carry & a);
: }
u**r
发帖数: 663
9
我的意思是++i应该不能用。

【在 c****p 的大作中提到】
: 慢。
: O(n) VS O(logn)的区别。
f********e
发帖数: 166
10
这个更牛啊，长见识了

【在 g*****i 的大作中提到】
: 这个复杂度偏高,careercup上有更快的,类似这样吧:
: result=x^y;
: carry=(x&y)<<1;
: while(carry != 0){
: temp=result^carry;
: carry=(result&carry)<<1;
: result=temp;
: }
相关主题
● one C++ question● one C++ question
● C++ object size一问● 发个题目给大家复习一下marco
● One C++ question● Why I can't compile this function successfully
进入JobHunting版参与讨论
e***s
发帖数: 799
11
赞！ 我的CODE可以歇一边去了

【在 g*****i 的大作中提到】
: 这个复杂度偏高,careercup上有更快的,类似这样吧:
: result=x^y;
: carry=(x&y)<<1;
: while(carry != 0){
: temp=result^carry;
: carry=(result&carry)<<1;
: result=temp;
: }
e***s
发帖数: 799
12
照葫芦画瓢，写了个减法的。 请教一下怎么验证result不能大于MAX_INT和小于MIN_
INT
public static int Subtract(int x, int y)
{
int result = x ^ y;
int borrow = (x ^ (x | y)) << 1;
int temp;
while (borrow != 0)
{
temp = result ^ borrow;
borrow = (result ^ (result | borrow)) << 1;
result = temp;
}
return result;
}
g*****i
发帖数: 2162
13
减法实现可以基于加法
sub(int a, int b){
return add(a, add(~b, 1));
}
e*****w
发帖数: 144
14
我也发个加法：
#include
using namespace std;
int Add(int a, int b) {
return (b ? Add(a ^ b, (a & b) << 1) : a);
}
int main() {
cout << "Add(3, 4) = " << Add(3, 4) << endl;
cout << "Add(3, -8) = " << Add(3, -8) << endl;
cout << "Add(-8, 40) = " << Add(-8, 40) << endl;
}
e*****w
发帖数: 144
15
加减乘，没用+-*/号。
#include
using namespace std;
int Add(int a, int b) {
return (b ? Add(a ^ b, (a & b) << 1) : a);
}
int Sub(int a, int b) {
return Add(a, Add(~b, 1));
}
int Mul(int a, int b) {
if (b == 0) return 0;
if (b < 0) return Mul(Sub(0, a), Sub(0, b));
return Add(a, Mul(a, Sub(b, 1)));
}
int main() {
cout << "Add(3, 4) = " << Add(3, 4) << endl;
cout << "Add(3, -8) = " << Add(3, -8) << endl;
cout << "Add(-8, 40) = " << Add(-8, 40) << endl;
cout << "Sub(3, 4) = " << Sub(3, 4) << endl;
cout << "Sub(3, -8) = " << Sub(3, -8) << endl;
cout << "Sub(-8, 40) = " << Sub(-8, 40) << endl;
cout << "Mul(3, 4) = " << Mul(3, 4) << endl;
cout << "Mul(3, -8) = " << Mul(3, -8) << endl;
cout << "Mul(-8, 40) = " << Mul(-8, 40) << endl;
}
$ ./a.out
Add(3, 4) = 7
Add(3, -8) = -5
Add(-8, 40) = 32
Sub(3, 4) = -1
Sub(3, -8) = 11
Sub(-8, 40) = -48
Mul(3, 4) = 12
Mul(3, -8) = -24
Mul(-8, 40) = -320
j*******l
发帖数: 1066
16
int Div(int a, int b) {
try{
if (b == 0) {
throw runtime_error("divisor is 0");
}
if( (a>0&&b<0) || (a>0&&b<0) ){
int sign = -1;
if(a<0){
a= Mul(-1,a);
}
if(b<0){
b= Mul(-1,b);
}
return Mul(sign, Div(a,b));
}
if(a<0){
a= Mul(-1,a);
}
if(b<0){
b= Mul(-1,b);
}
return (a }catch (runtime_error err){
cerr< return 0;
}
}
Div(6, 3) = 2
Div(6, -3) = -2
Div(-6, 3) = 2
Div(-6, -3) = 2
Div(0, -3) = 0
Div(0, 3) = 0
divisor is 0
Div(0, 0) = 0
Div(10, 3) = 3
Div(10, -3) = -3
Div(-10, 3) = 3
Div(-10, -3) = 3
e***s
发帖数: 799
17
学习了，赞～

【在 e*****w 的大作中提到】
: 加减乘，没用+-*/号。
: #include
: using namespace std;
: int Add(int a, int b) {
: return (b ? Add(a ^ b, (a & b) << 1) : a);
: }
: int Sub(int a, int b) {
: return Add(a, Add(~b, 1));
: }
: int Mul(int a, int b) {
g*****i
发帖数: 2162
18
*/的思路应该是位移运算,每次*2,比用+-快多了
w*******s
发帖数: 96
19
How to implement + - * / without arithmetic operation?
e***s
发帖数: 799
20
int add(int x, int y) {
int carry = 0;
int result = 0;
int i;
for(i = 0; i < 32; ++i) {
int a = (x >> i) & 1;
int b = (y >> i) & 1;
result |= ((a ^ b) ^ carry) << i;
carry = (a & b) | (b & carry) | (carry & a);
}
return result;
}
相关主题
● C++: what is the output? How to interpret it?● C++问题
● C++ Q42: (C22)● 弱问个C++ 问题 （const_cast）
● 问个c++题● 新手问个C++（Thinking in C++ source code）
进入JobHunting版参与讨论
f********e
发帖数: 166
21
赞楼上的代码!
y*******g
发帖数: 6599
22
++i不算arithmetic？

【在 e***s 的大作中提到】
: int add(int x, int y) {
: int carry = 0;
: int result = 0;
: int i;
: for(i = 0; i < 32; ++i) {
: int a = (x >> i) & 1;
: int b = (y >> i) & 1;
: result |= ((a ^ b) ^ carry) << i;
: carry = (a & b) | (b & carry) | (carry & a);
: }
f********e
发帖数: 166
23
照葫芦画瓢实现了个减法,调用加法，我觉得++不算算术运算符吧，除了+,-.*,/吧
int substract(int x, int y) {
int carry = 0;
int result = 0;
int t = ~y;
t = add(t,1); //t 是y 的相反数
for(int i = 0; i < 32; ++i) {
int a = (x >> i) & 1;
int b = (t >> i) & 1;
result |= ((a ^ b) ^ carry) << i;
carry = (a & b) | (b & carry) | (carry & a);
}
return result;
}
u**r
发帖数: 663
24
++i不算的话，你int x +　int y直接用++x循环就完了。
c****p
发帖数: 6474
25
慢。
O(n) VS O(logn)的区别。

【在 u**r 的大作中提到】
: ++i不算的话，你int x +　int y直接用++x循环就完了。
g*****i
发帖数: 2162
26
这个复杂度偏高,careercup上有更快的,类似这样吧:
result=x^y;
carry=(x&y)<<1;
while(carry != 0){
temp=result^carry;
carry=(result&carry)<<1;
result=temp;
}

【在 e***s 的大作中提到】
: int add(int x, int y) {
: int carry = 0;
: int result = 0;
: int i;
: for(i = 0; i < 32; ++i) {
: int a = (x >> i) & 1;
: int b = (y >> i) & 1;
: result |= ((a ^ b) ^ carry) << i;
: carry = (a & b) | (b & carry) | (carry & a);
: }
u**r
发帖数: 663
27
我的意思是++i应该不能用。

【在 c****p 的大作中提到】
: 慢。
: O(n) VS O(logn)的区别。
f********e
发帖数: 166
28
这个更牛啊，长见识了

【在 g*****i 的大作中提到】
: 这个复杂度偏高,careercup上有更快的,类似这样吧:
: result=x^y;
: carry=(x&y)<<1;
: while(carry != 0){
: temp=result^carry;
: carry=(result&carry)<<1;
: result=temp;
: }
e***s
发帖数: 799
29
赞！ 我的CODE可以歇一边去了

【在 g*****i 的大作中提到】
: 这个复杂度偏高,careercup上有更快的,类似这样吧:
: result=x^y;
: carry=(x&y)<<1;
: while(carry != 0){
: temp=result^carry;
: carry=(result&carry)<<1;
: result=temp;
: }
e***s
发帖数: 799
30
照葫芦画瓢，写了个减法的。 请教一下怎么验证result不能大于MAX_INT和小于MIN_
INT
public static int Subtract(int x, int y)
{
int result = x ^ y;
int borrow = (x ^ (x | y)) << 1;
int temp;
while (borrow != 0)
{
temp = result ^ borrow;
borrow = (result ^ (result | borrow)) << 1;
result = temp;
}
return result;
}
相关主题
● 新手请教：C++ decrement loop (转载)● amazon的那道题目
● c++ 程序一问● Interview questions, Bloomberg
● 请教一道面试题,关于tree的● 一个容易记忆的permutation算法
进入JobHunting版参与讨论
g*****i
发帖数: 2162
31
减法实现可以基于加法
sub(int a, int b){
return add(a, add(~b, 1));
}
e*****w
发帖数: 144
32
我也发个加法：
#include
using namespace std;
int Add(int a, int b) {
return (b ? Add(a ^ b, (a & b) << 1) : a);
}
int main() {
cout << "Add(3, 4) = " << Add(3, 4) << endl;
cout << "Add(3, -8) = " << Add(3, -8) << endl;
cout << "Add(-8, 40) = " << Add(-8, 40) << endl;
}
e*****w
发帖数: 144
33
加减乘，没用+-*/号。
#include
using namespace std;
int Add(int a, int b) {
return (b ? Add(a ^ b, (a & b) << 1) : a);
}
int Sub(int a, int b) {
return Add(a, Add(~b, 1));
}
int Mul(int a, int b) {
if (b == 0) return 0;
if (b < 0) return Mul(Sub(0, a), Sub(0, b));
return Add(a, Mul(a, Sub(b, 1)));
}
int main() {
cout << "Add(3, 4) = " << Add(3, 4) << endl;
cout << "Add(3, -8) = " << Add(3, -8) << endl;
cout << "Add(-8, 40) = " << Add(-8, 40) << endl;
cout << "Sub(3, 4) = " << Sub(3, 4) << endl;
cout << "Sub(3, -8) = " << Sub(3, -8) << endl;
cout << "Sub(-8, 40) = " << Sub(-8, 40) << endl;
cout << "Mul(3, 4) = " << Mul(3, 4) << endl;
cout << "Mul(3, -8) = " << Mul(3, -8) << endl;
cout << "Mul(-8, 40) = " << Mul(-8, 40) << endl;
}
$ ./a.out
Add(3, 4) = 7
Add(3, -8) = -5
Add(-8, 40) = 32
Sub(3, 4) = -1
Sub(3, -8) = 11
Sub(-8, 40) = -48
Mul(3, 4) = 12
Mul(3, -8) = -24
Mul(-8, 40) = -320
j*******l
发帖数: 1066
34
int Div(int a, int b) {
try{
if (b == 0) {
throw runtime_error("divisor is 0");
}
if( (a>0&&b<0) || (a>0&&b<0) ){
int sign = -1;
if(a<0){
a= Mul(-1,a);
}
if(b<0){
b= Mul(-1,b);
}
return Mul(sign, Div(a,b));
}
if(a<0){
a= Mul(-1,a);
}
if(b<0){
b= Mul(-1,b);
}
return (a }catch (runtime_error err){
cerr< return 0;
}
}
Div(6, 3) = 2
Div(6, -3) = -2
Div(-6, 3) = 2
Div(-6, -3) = 2
Div(0, -3) = 0
Div(0, 3) = 0
divisor is 0
Div(0, 0) = 0
Div(10, 3) = 3
Div(10, -3) = -3
Div(-10, 3) = 3
Div(-10, -3) = 3
e***s
发帖数: 799
35
学习了，赞～

【在 e*****w 的大作中提到】
: 加减乘，没用+-*/号。
: #include
: using namespace std;
: int Add(int a, int b) {
: return (b ? Add(a ^ b, (a & b) << 1) : a);
: }
: int Sub(int a, int b) {
: return Add(a, Add(~b, 1));
: }
: int Mul(int a, int b) {
g*****i
发帖数: 2162
36
*/的思路应该是位移运算,每次*2,比用+-快多了
e***s
发帖数: 799
37
按照guangyi的提示写了一个MUL的, 应该是比一个一个加起来快一点
public static int mul(int a, int b)
{
int result = 0;
bool neg = false;
if (b < 0)
{
neg = true;
b = add(~b, 1);
}
if (b == 0)
return 0;
while (b > 1)
{
if ((b & 1) == 1)
result = add(result, a);
b >>= 1;
a <<= 1;
}
result = add(result, a);
if (neg)
return result = add(~result, 1);
else
return result;
}

【在 g*****i 的大作中提到】
: */的思路应该是位移运算,每次*2,比用+-快多了
e***s
发帖数: 799
38
@guangyi, 请教DIV的移位方法的CODE。
1 (共1页)
进入JobHunting版参与讨论
相关主题
● 弱问个C++ 问题 （const_cast）● 好记(但不是最优)的combination算法
● 新手问个C++（Thinking in C++ source code）● one C++ question
● 新手请教：C++ decrement loop (转载)● C++ object size一问
● c++ 程序一问● One C++ question
● 请教一道面试题,关于tree的● one C++ question
● amazon的那道题目● 发个题目给大家复习一下marco
● Interview questions, Bloomberg● Why I can't compile this function successfully
● 一个容易记忆的permutation算法● C++: what is the output? How to interpret it?
相关话题的讨论汇总
话题: int话题: add话题: div话题: mul话题: result

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑