e*s
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;
}
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
3 楼
赞楼上的代码!
f*e
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;
}
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
6 楼
++i不算的话,你int x + int y直接用++x循环就完了。
g*i
8 楼
这个复杂度偏高,careercup上有更快的,类似这样吧:
result=x^y;
carry=(x&y)<<1;
while(carry != 0){
temp=result^carry;
carry=(result&carry)<<1;
result=temp;
}
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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);
: }
result=x^y;
carry=(x&y)<<1;
while(carry != 0){
temp=result^carry;
carry=(result&carry)<<1;
result=temp;
}
【在 e***s 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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);
: }
e*s
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;
}
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
13 楼
减法实现可以基于加法
sub(int a, int b){
return add(a, add(~b, 1));
}
sub(int a, int b){
return add(a, add(~b, 1));
}
e*w
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;
}
#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
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
#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
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
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<
}
}
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
g*i
18 楼
*/的思路应该是位移运算,每次*2,比用+-快多了
w*s
19 楼
How to implement + - * / without arithmetic operation?
e*s
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;
}
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
21 楼
赞楼上的代码!
f*e
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;
}
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
24 楼
++i不算的话,你int x + int y直接用++x循环就完了。
g*i
26 楼
这个复杂度偏高,careercup上有更快的,类似这样吧:
result=x^y;
carry=(x&y)<<1;
while(carry != 0){
temp=result^carry;
carry=(result&carry)<<1;
result=temp;
}
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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);
: }
result=x^y;
carry=(x&y)<<1;
while(carry != 0){
temp=result^carry;
carry=(result&carry)<<1;
result=temp;
}
【在 e***s 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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);
: }
e*s
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;
}
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
31 楼
减法实现可以基于加法
sub(int a, int b){
return add(a, add(~b, 1));
}
sub(int a, int b){
return add(a, add(~b, 1));
}
e*w
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;
}
#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
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
#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
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
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<
}
}
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
g*i
36 楼
*/的思路应该是位移运算,每次*2,比用+-快多了
e*s
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: */的思路应该是位移运算,每次*2,比用+-快多了
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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: */的思路应该是位移运算,每次*2,比用+-快多了
e*s
38 楼
@guangyi, 请教DIV的移位方法的CODE。
相关阅读
宝妈问一个h1b填表的问题靠, linkedin密码泄漏了。求问AMAZON Technical program manager for NEW GRADonsite快20天了,煎熬中……大家看看这样做合适不合适问个题 weighted random sampling问个关于H1b transfer的问题马上电面,紧张呀,求blessFacebook 的 CEO 人品好像不怎样?要不要去面试请问大家recruiting incentive是啥Seeking a couple of Java developers for Google Mountain Vi转h1b与offer cancel的问题统计真是个low pay 的行业啊听说bb不裁人 历史上提个醒, 关于same day delivery[H1B] 现在开始电面, 然后onsite, 还能赶上今年的H1B吗?给我办H1b的律师度假去了有哪位了解criminal check国内部分是怎么操作的吗?经济好转了?