| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2457 人关注过本帖, 2 人收藏
标题:关于位运算的一个题目,高手请进
只看楼主 加入收藏
hgand
Rank: 2
等 级:论坛游民
帖 子:32
专家分:77
注 册:2012-10-17
收藏
得分:0 
10楼你写反了吧,左移是乘,右移是除啊!
2012-10-25 09:12
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
cyhdahua的解释基本是我算法的本意。

如果各位觉得明白了,那不妨再测试一下自己的理解程度,请偿试用位运算完成任意两个整数(整型范围内的)的乘法运算。

话说cyhdahua这头像,我差点以为是佟湘玉

重剑无锋,大巧不工
2012-10-25 20:57
经哥
Rank: 3Rank: 3
来 自:代码空间
等 级:论坛游侠
威 望:1
帖 子:289
专家分:124
注 册:2012-9-8
收藏
得分:0 
回复 8楼 hgand
有一个错误 哦,i<n后面是分号吧?

我只是个演员,还是业余的!!
2012-10-25 21:24
罗庇鹏ksq
Rank: 5Rank: 5
来 自:太平洋
等 级:职业侠客
帖 子:220
专家分:310
注 册:2012-6-30
收藏
得分:0 
n << 3是二进制左移3位,即相当于乘了8,接下来只需要加一倍,而又不能用加减。
对于a^n,此为a与n进行位异或
1^1=0^0=0
0^1=1^0=1
a^n如果没出现两个1在同一位,也就是a&n=0,那么结果就是加了一倍,所以立即跳出循环
得出答案
有两个1同一位则:f记录了同一位的位子,用1记录,其他为零,接下来就是为了让有两个1的进一位。
a^=n是a=a^n可以看成在循环体中循环
n=f<<1也可看成是在内部循环
n存的即为有1位的位子(即f)左移一位,相当于进一位
a=a^n是让新存的n再与a异或,即相当于相加(如果没有两个1同位),如果又同位的再继续循环知道最后f=0,跳出。求得。
我的理解。谢谢杨大哥指点迷津,我想想两个整数乘去。


从来都是无所谓,现在也该学着有所谓。✿咱们一个人,别坐井观天❀
2012-10-25 23:01
cyhdahua
Rank: 7Rank: 7Rank: 7
来 自:山东
等 级:黑侠
威 望:2
帖 子:221
专家分:643
注 册:2012-6-15
收藏
得分:0 
回复 32楼 beyondyf
理解归理解,但能用代码写出来是另一回事
程序代码:
#include<stdio.h>
//用位运算直接实现两数相乘
/*思路:
    1.判断正负号
    2.把负数转换成正数
    3.正数2进制乘法,即
            110
           *101
           ------
            110
         + 000
         +110
     就是一个数如果左移n位,并且最低位是1,那么另一个数就右移n位。
     然后把右移后的结果相加
     4.加上符号
*/
int mult_bit(int n,int m){
    bool sign;    //=n<0?(m<0? n=-n,m=-m,true:n=-n,false):(m>0?true:m=-m,false);  //同号为true,并且把m,n转成正数(直接赋值为什么不行?)
    if(n<0&&m<0||n>0&&m>0){
        sign=true;
        n<0?n=-n:n;
        m<0?m=-m:m;
    }
    else{
        sign=false;
        n<0?n=-n:n;
        m<0?m=-m:m;
    }
    int sum=0,temp=0,f;
    for(int i=0;f=m>>i;i++){
        if(f&1)temp=n<<i;else continue;
        for(;f=sum&temp;sum^=temp,temp=f<<1);
        sum^=temp;
    }
    return sign?sum:-sum;
}
int main(){
    int a,b;
    printf("Input two integer:");
    while(scanf("%d%d",&a,&b))
        printf("%d\nGO ON:\n",mult_bit(a,b));
    return 0;
}
已经很努力了,求指点,求改进

WE GO
2012-10-26 23:20
cyhdahua
Rank: 7Rank: 7Rank: 7
来 自:山东
等 级:黑侠
威 望:2
帖 子:221
专家分:643
注 册:2012-6-15
收藏
得分:0 
程序代码:
#include<stdio.h>
#include<math.h>
//用位运算直接实现两数相乘
/*思路:
    1.判断正负号
    2.把负数转换成正数
    3.正数2进制乘法,即
            110
           *101
           ------
            110
         + 000
         +110
     就是一个数如果左移n位,并且最低位是1,那么另一个数就右移n位。
     然后把右移后的结果相加
     4.加上符号
*/
int mult_bit(int n,int m){
    int sum=0,temp=0,f;
    n=abs(n),m=abs(m);
    for(int i=0;f=m>>i;i++){
        if(f&1)temp=n<<i;else continue;
        for(;f=sum&temp;sum^=temp,temp=f<<1);
        sum^=temp;
    }
    return (n^m)<0?-sum:sum;
}
int main(){
    int x;  x=-13.06;
    int a,b;
    printf("Input two integer:");
    while(scanf("%d%d",&a,&b))
        printf("%d\nGO ON:\n",mult_bit(a,b));
    return 0;
}
再贴一次

WE GO
2012-10-27 08:12
lylhe
Rank: 1
等 级:新手上路
帖 子:7
专家分:4
注 册:2012-10-18
收藏
得分:0 
回复 26楼 cyhdahua
关于&位,你是否理解错了? 1&0=0吧,而不是1!
2012-10-27 08:33
cyhdahua
Rank: 7Rank: 7Rank: 7
来 自:山东
等 级:黑侠
威 望:2
帖 子:221
专家分:643
注 册:2012-6-15
收藏
得分:0 
回复 37楼 lylhe
请详细一点

WE GO
2012-10-27 09:02
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 36楼 cyhdahua
基本思路没有问题,只是没有必要进行符号处理。通过这个题目大家应该好好感受一下补码的真谛。

既然湘玉对这个问题这么热情,那我也奉上我的代码和大家交流。

再留给大家一个思考题,我的mul函数计算用变量用的是无符号整型,返回值却是有符号整型。这么做意义何在?有没有问题?

程序代码:
#include<stdio.h>

int mul(unsigned int a, unsigned int b)
{
    unsigned int c, f, t;
    for(c = 0; a && b; c ^= t, a <<= 1, b >>= 1)
    for(t = b & 1 ? a : 0; f = c & t; c ^= t, t = f << 1);
    return c;
}

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d * %d = %d\n", a, b, mul(a, b));
    return 0;
}

重剑无锋,大巧不工
2012-10-27 09:33
madfrogme
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:21
帖 子:1160
专家分:1106
注 册:2009-6-24
收藏
得分:0 
以下是引用beyondyf在2012-10-27 10:33:19的发言:

基本思路没有问题,只是没有必要进行符号处理。通过这个题目大家应该好好感受一下补码的真谛。

既然湘玉对这个问题这么热情,那我也奉上我的代码和大家交流。

再留给大家一个思考题,我的mul函数计算用变量用的是无符号整型,返回值却是有符号整型。这么做意义何在?有没有问题?

#include
 
int mul(unsigned int a, unsigned int b)
{
    unsigned int c, f, t;
    for(c = 0; a && b; c ^= t, a <<= 1, b >>= 1)
    for(t = b & 1 ? a : 0; f = c & t; c ^= t, t = f << 1);
    return c;
}
 
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d * %d = %d\n", a, b, mul(a, b));
    return 0;
}
想了还是不明白为什么是无符号整形和有有符号整形,

不过我想问一个无关的问题

t 是不是要初始化一下? 比如 3 & 4 =0 接下来 c ^=t  ,所以t 是不是要初始化一下,

虽然t不是很明白在这里是什么用途,还望大家明示


[ 本帖最后由 madfrogme 于 2012-10-27 16:17 编辑 ]

The quieter you become, the more you can hear
2012-10-27 15:14
快速回复:关于位运算的一个题目,高手请进
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.047489 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved