逻辑表达式 (a+b)&~b 的含义 它实现了什么?

这个表达式实现了什么,有什么作用?希望给讲一下,谢谢大家了... 这个表达式实现了什么,有什么作用? 希望给讲一下,谢谢大家了 展开
 我来答
追忆__ac
2019-11-08
知道答主
回答量:0
采纳率:0%
帮助的人:0
展开全部

上面的zjuzzh317大佬回答的很好了,但还是想补充下....

设f(a,b) = (a+b-1)&~(b-1),f(11,6) = 16,此时16 并不能整除6,但是b为2的幂时上式是确实可行的。可以参照下面代码跑一下。那么如何证明这个结论呢,首先b如果是2的幂此时b-1应该按2进制如下排列,这里设a>0,b>1。

b-1 b

1    10

11  100

111 1000

1111 10000

...

~将其取反则此时非0位全部为1,则&的意思很明确了,就是在高位上取一些左值对应位也为1的。设c = a+b-1,c>a,c&~(b-1)是如何保证其值是b的倍数呢,按照我们上面的分析,b在二进制中只有一位为1,我们设这个位置是p,则b=2的p-1次方,OK,那么~(b-1)保证了这些可取的高位一定是b的倍数,如111 1000,~111实际上是11111...000,如果你熟悉二进制,那么很显然前面那些1,我只要取一个就肯定是1000的倍数了。OK,那么我们如何保证c&~(b-1),一定会有一个1取到呢?也很容易分析:

先写下隐藏条件:c>a,c>b。

c>b,意味着存在比p要高或者相同的位中有一个为1。以上说明了f的值是b的倍数。那么如何保证f的值是a的上界,且是最小的?想想看还有哪个式子没用到?显然是c>a,c>a这个式子意味着什么呢?实际上和上面哪个思想类似,因为c>a,而且c&~(b-1),这个~(b-1)左边所有的位都是1,那么我们把a+b-1分成两种情况:第一种,在第p位中有进位的情况(说明下第p位进位是什么意思,省的产生误会,我这里假设进位的意思是两个数二进制下相加,第p位往上进1,则wo们称第p位有进位)此时说明了什么?

是不是在p位或者p+1...p+2..这些位上进位了?OK,进位不就意味着c&~(b-1)>a了吗。在第p位没产生进位,这是什么情况呢?实际上,b-1,中p以下的低位是不是都是1呢,如果不进位,肯定意味着a在p以下的低位根本没有1,而此时我们用c&~(b-1)就等于a。这样,就证明了c&~(b-1)一定是a的弱上界,即f > a,上面我们还能得到f<=c,这里为啥写出来呢?下面要用到哈哈,

f<=c,实际上也很容易看出来,只需要考虑第一种情况,进位时,可能存在c中有比第p位的更低位为1,而&使得c中的这些位置为0了,其余位自然不变,因此f<=c。

现在我们只差最后一步了,即是证明f的值一定是a的最小弱上界,这里弱的意思就是说这个值可以是a。显然我们只需要考虑第p位存在进位的情况,假设我们存在一个更小的下界d,d是b的倍数,且d<f,那么我们应该要找到一个k>0,使得d = f - k,这时f-k在二进制下会发生什么情况呢,因为f是b的倍数,所以p位以下必全0,所以k的p位以下也一定要是一个全0的情况,否则这会使得f-k不是b的倍数。但是k>0,那么k必定要有在p位或p位以上的某些位为1,这不就说明k >= b了吗,这里我们就可以想到前提条件d >= a了,如果d >= a则f-k >= a,即f >= a + k,即

f >= a + b,这与f<=c矛盾了,因此并不存在一个更小弱上界了。

综上,f(a,b)是b的倍数,且f(a,b)是a的一个最小弱上界。

这里还遗留一个问题,也就是我们最开始说到的,b为什么一定要是2的幂?如果不是2的幂,则b-1,无法产生p位以下全1的情况,~(b-1)也无法产生p位以上全1的情况,此时上面的证明失效。例如f(25,6) = 26。


#include <unistd.h>

#include <stdio.h>

void fun(int a,int b){

    printf("%d\n",(a+b-1)&~(b-1));

}

int main(){

    int a,b;

    while(~scanf("%d%d",&a,&b)){

        fun(a,b);

    }

    return 0;

}

在鉴湖准备烛光晚餐的徐晃
2019-05-31
知道答主
回答量:2
采纳率:0%
帮助的人:1486
展开全部
先给个例子吧,假设4位十进制数
a = 7,b = 3
(0111 + 0011) & (~0011)
= (1010)&(1100) = 1000
得到的结果是8
同样的
(21 + 7)&(~7)= 24
(010101 + 000111)&(111000) = (011100)&(111000) = (011000) = 24
这个逻辑式子的作用由例子可以看出一点点
8 是 4(b+1)的倍数中7的最小上界,
24是8(7 + 1)的倍数中21的最小上界。
逻辑表达式的作用是求出在b + 1的倍数中a的最小上界
证明过程比较复杂。。。此处略去
写完之后发现是个非常老的问答了。。。还是发上来吧,希望对大家有帮助
如果你觉得有用的话,不妨给个赞呗。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
云在天7R
2015-04-30 · 超过11用户采纳过TA的回答
知道答主
回答量:38
采纳率:0%
帮助的人:25.8万
展开全部
按位与运算符(&)
参加运算的两个数据,按二进制位进行“与”运算。
运算规则:0&0=0; 0&1=0; 1&0=0; 1&1=1;
即:两位同时为“1”,结果才为“1”,否则为0
例如:3&5 即 0000 0011 & 0000 0101 = 0000 0001 因此,3&5的值得1。
按位取反运算符“~”是一个单目运算符,能对一个二进制数的每一位都取反,即 0 变 为 1,1 变为 0。例如:
a= 0 0 0 1 1 0 1 0 /*十六进制为 1a*/ ~ a= 1 1 1 0 0 1 0 1 
/*十六进制为 e5*/ 
追问
(a+b)&~b
实现了啥功能 它也不是胡乱的 操作一下啊
本回答被网友采纳
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
srl11
2018-05-11 · TA获得超过119个赞
知道答主
回答量:22
采纳率:0%
帮助的人:5.9万
展开全部
感觉原式应该是: (a+b-1)&~(b-1)。
这里表示对a上取b的整数倍。例如 a=21, b=32, 则得到的返回值应为 32;a=33, b=32,则得到的返回值应为64。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 1条折叠回答
收起 更多回答(2)
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式