首页 / JAVA / java-累积按位运算
java-累积按位运算
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java-累积按位运算,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1212字,纯文字阅读大概需要2分钟。
内容图文
![java-累积按位运算](/upload/InfoBanner/zyjiaocheng/669/22a6088d50b440129f8e9cafae84a776.jpg)
假设您有一个数组A = [x,y,z,…]
然后,您计算一个前缀/累积的BITWISE-OR数组P = [x,x | y,x | y | z,…]
如果我想找到索引1和索引6之间的元素的BITWISE-OR,如何使用此预先计算的P数组来做到这一点?可能吗?
我知道它可以累积总和来获得一定范围内的总和,但是我不确定使用位运算.
编辑:A中允许重复,因此A = [1、2、2、2、2、3]是可能的.
解决方法:
无法使用前缀/累积的BITWISE-OR数组来计算某个随机范围的按位或,您可以尝试使用2个元素的简单情况并进行验证.
但是,有不同的方法,它利用前缀和.
假设我们正在处理32位整数,我们知道,对于范围x到y的按位或和,如果范围(x,y)中存在一个具有第i个数字的结果,则结果的第i位将为1位是1.因此,通过反复回答以下查询:
>范围(x,y)中是否有第i位设置为1的数字?
我们可以形成问题的答案.
那么,如何检查在(x,y)范围内至少有一个第ith个位设置了呢?我们可以预处理并填充数组pre [n] [32],该数组包含数组中所有32位的前缀和.
for(int i = 0; i < n; i++){
for(int j = 0; j < 32; j++){
//check if bit i is set for arr[i]
if((arr[i] && (1 << j)) != 0){
pre[i][j] = 1;
}
if( i > 0) {
pre[i][j] += pre[i - 1][j];
}
}
}
并且,检查是否设置了位i,范围(x,y)等于检查是否:
pre[y][i] - pre[x - 1][i] > 0
重复此检查32次以计算最终结果:
int result = 0;
for (int i = 0; i < 32; i++){
if((pre[y][i] - (i > 0 ? pre[x - 1][i] : 0)) > 0){
result |= (1 << i);
}
}
return result;
内容总结
以上是互联网集市为您收集整理的java-累积按位运算全部内容,希望文章能够帮你解决java-累积按位运算所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。