勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

一个问题,如何优化? 是否有高效的算法

        问题描述如下:
                2个整数(int32),我需要对这2个数的第n位进行二进制数交换值。是否有一个高效的算法,或者高效的运算。

                例子如下:

                2个整数10,7,把第1位的数值交换。

               整数          二进制        交换后二进制       交换后的值

                10             0x1010        0x1011                   11

                7               0x0111        0x0110                   6

               

             我的思路如下:

              1.如果要对第n位数值交换,先求出第n位的值(1或者0),如果相等则不交换。

              2.交换第n位,通过通过原理发现只需通过加减法运算即可,如果1->0 则减   1<<(n-1)  ,否则加1<<(n-1)。

代码如下:

 1void   prjfun( int & des , int & src , int n)
 2{
 3    if( n <= 0 ) return ;
 4
 5    int x = (des & (1<<(n-1))) >>(n-1);   // 求出第n位的数值
 6    int y = (src & (1<<(n-1))) >>(n-1);   // 求出第n位的数值
 7    if ( x != y )
 8    {
 9        des += (y-x)*(1<<(n-1));          // 交换
10        stc += (x-y)*(1<<(n-1));          // 交换
11    }

12}

 

           是否有一种高效的算法,只是进行一,两步位与或运算即可。。

        

posted on 2009-10-18 22:27 expter 阅读(1933) 评论(13)  编辑 收藏 引用 所属分类: 其他学习笔记工作笔记算法与数据结构

评论

# re: 一个问题,如何优化? 是否有高效的算法[未登录] 2009-10-18 23:43 Eric

你可以试试这样
int mask[32]={0x1,0x2,0x4,0x8,0x10...........};
void fun( int & a , int & b , int n )
{
int c=mask[n-1];
if ( ( a&c )!=( b&c ) ) {
a=a^c;
b=b^c;
}
}  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法 2009-10-18 23:56 夜风

你这个算法有很多是多余的,而且位运算就少用+、-,看看下面的算法,感觉不错哦
bool prjfun( int & des , int & src , int n)
{
if(n <= 0)
return false;
int mask = 1 << (n-1);
if((des & mask) != (src & mask))
{
des ^= mask;
src ^= mask;
}
return true;
}  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法 2009-10-19 00:19 lucifer

可以不需要if判断语句的,
void prjfun( int & des , int & src , int n)
{
if( n <= 0 ) return ;

int x=(des&(1<<(n-1)))-(src&(1<<(n-1)));
des-=x;
src+=x;
}  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法 2009-10-19 09:09 Fox

支持@Eric
  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法[未登录] 2009-10-19 10:23 alex-lee

Eric算法好  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法 2009-10-19 12:40 wangjinhu

void f(int& a,int& b,int n)
{
int c = a&(1<<n);
a = (a&(~(1<<n)))|(b&(1<<n));
b = (b&(~(1<<n)))|c;
}
这样多整齐啊,要是要判断n
那也得
if(n<0 || n>31)吧  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法 2009-10-19 14:55 淘宝皇冠店

感觉不错哦  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法[未登录] 2009-10-19 16:58 vincent

eric  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法[未登录] 2009-10-19 17:29 goteet

& | 是基本把  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法[未登录] 2009-10-19 20:01 Eric

@Eric
我想了下,条件判断还是可以去掉的:
int mask[33]={0,0x1,0x2,0x4,0x8,0x10......};
void fun( int & a , int & b , int n )
{
int c=(a^b)&mask[n];
a^=c;
b^=c;
}  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法 2009-10-19 20:26 expter

@Eric
@wangjinhu
的方法不错,学习了。。。  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法 2009-10-21 12:59 阿福

我有一种办法,应该是最快的:
把显示器倒过来,哈哈!  回复  更多评论   

# re: 一个问题,如何优化? 是否有高效的算法 2009-10-22 09:29 李佳

楼上很风趣   回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理