Javaビット演算セクション
5541 ワード
2019新春支付宝紅包技術大揭秘オンラインサミットは03-07日から始まり、ここをクリックして申し込むと大牛インタラクティブに参加することができる.
ビット演算式はオペランドとビット演算子からなり,整数型のバイナリ数のビット演算を実現する.ビット演算子は、論理演算子(~、&、|および^を含む)およびシフト演算子(>>、<>)に分けることができる.
ビット演算を行う場合は、次の点に注意してください.
ビット演算子の優先順位
ビット演算の応用
1.int型変数aが奇数か偶数かを判断する
2.平均値を求める.例えば、2つのintタイプ変数x,yがあり、まずx+yの和を要求し、2で割るが、x+yの結果がintの最大表現範囲を超える可能性がある.
3.0より大きい整数について、それが2の何次方であるかを判断する
4.例えば2つのint型変数x,yがあり、両者のデジタル交換、ビット演算を要求する実現方法
5.絶対値を求める
6.型取り演算、ビット演算で実現
7.乗算はビット演算で実現
8.除算演算をビット演算に変換
9.逆数を求める
10.a%2は
11.int型変数aのk番目(k=0,1,2…sizeof(int))をとる
12.int型変数aのk番目を0にクリアする
13.int型変数aのk番目の位置1を
14.int型変数ループ左シフトk回
15.int型変数aループ右シフトk回
16.1つの数x>=0について、2のべき乗であるか否かを判定する.
17.tempで2つの整数を交換しない
18.条件判断賦値簡写
19.xの逆数
20.mに2を乗じたn次方
21.mを2で割ったn次方
22.整数kを求めてx位(高い)からy位(低い)の間に何個の1があります
23.絶対値をとる
24.1回の数値のみが空でない整数配列を与え、ある要素が1回しか現れない以外は、各要素が2回現れる.それが一度しか現れなかった要素を見つけます.説明:あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?例1:
例2:
この問題でまず思いついたのは異或の特性だ.同じ数字の異和の結果が0であれば、奇数回現れるのは最後に私たちが望んだ結果に違いない.
まとめ
機能
例
ビット演算
最下位を外す
(101101->10110)
x >> 1
最後に0を追加
(101101->1011010)
x << 1
最後に1を追加
(101101->1011011)
x << 1+1
最下位を1にする
(101100->101101)
x | 1
最下位を0にする
(101101->101100)
x | 1-1
最後の取反
(101101->101100)
x ^ 1
右からk位を1にする
(101001->101101,k=3)
x | (1 << (k-1))
右からk位を0にする
(101101->101001,k=3)
x & ~ (1 << (k-1))
右からk番目の位置を逆にする
(101001->101101,k=3)
x ^ (1 << (k-1))
末尾3位をとる
(1101101->101)
x & 7
末k位をとる
(1101101->1101,k=5)
x & ((1 << k)-1)
右からk位をとる
(1101101->1,k=4)
x >> (k-1) & 1
末k位を1にする
(101001->101111,k=4)
x | (1 << k-1)
末k位取反
(101001->100110,k=4)
x ^ (1 << k-1)
右の連続する1を0にする
(100101111->100100000)
x & (x+1)
右から1番目の0を1にする
(100101111->100111111)
x | (x+1)
右の連続する0を1にする
(11011000->11011111)
x | (x-1)
右の連続する1をとる
(100101111->1111)
(x ^ (x+1)) >> 1
右から1番目の左を外す
(100101000->1000)
x & (x ^ (x-1))
判定奇数
(x&1)==1
けっていぐうすう
(x&1)==0
クリックして詳細を表示
ビット演算式はオペランドとビット演算子からなり,整数型のバイナリ数のビット演算を実現する.ビット演算子は、論理演算子(~、&、|および^を含む)およびシフト演算子(>>、<>)に分けることができる.
1) (<>) 。 “ ” “ ”: , 0; , 1。
3)Java “ ” (>>>), “ ”: , 0。 C C++ 。
4) char,byte short , , int。 5 。 int 。 long , long。 6 , long 。 “ ” , 。 byte short , (Java 1.0 Java 1.1 )。 int , 。 “ ” , -1 。
ビット演算を行う場合は、次の点に注意してください.
(1)>>> >> : ,>>> 0, >> 。
(2) 2, ( ) 2; 。
(3) , 。
(4) , 。
(5) , 。
(6) 1。
ビット演算子の優先順位
~ , <> >>>, &, ^, |。
ビット演算の応用
1.int型変数aが奇数か偶数かを判断する
a&1 == 0
a&1 == 1
2.平均値を求める.例えば、2つのintタイプ変数x,yがあり、まずx+yの和を要求し、2で割るが、x+yの結果がintの最大表現範囲を超える可能性がある.
(x&y)+((x^y)>>1);
:>>n 2^n ,<
3.0より大きい整数について、それが2の何次方であるかを判断する
((x&(x-1))==0)&&(x!=0);
/* 2 ,n 100... n-1 1111....
0*/
4.例えば2つのint型変数x,yがあり、両者のデジタル交換、ビット演算を要求する実現方法
x ^= y;
y ^= x;
x ^= y;
5.絶対値を求める
int abs( int x ) {
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
6.型取り演算、ビット演算で実現
a % (2^n) a & (2^n - 1) ; m % n m & (n-1)
7.乗算はビット演算で実現
a * (2^n) a << n
8.除算演算をビット演算に変換
a / (2^n) a>> n
9.逆数を求める
(~x+1)
10.a%2は
a & 1
11.int型変数aのk番目(k=0,1,2…sizeof(int))をとる
a>>k&1 ( 1)
12.int型変数aのk番目を0にクリアする
a&~(1<
13.int型変数aのk番目の位置1を
a|(1<
14.int型変数ループ左シフトk回
a<>16-k ( sizeof(int)=16)
15.int型変数aループ右シフトk回
a>>k|a<<16-k ( sizeof(int)=16)
16.1つの数x>=0について、2のべき乗であるか否かを判定する.
boolean isPower2(int x) {
return ((x&(x-1))==0) && (x!=0);
}
17.tempで2つの整数を交換しない
void swap(int x , int y) {
x ^= y;
y ^= x;
x ^= y;
}
18.条件判断賦値簡写
if (x == a)
x= b;
else
x= a;
x= a ^ b ^ x;
19.xの逆数
(~x+1)
20.mに2を乗じたn次方
m << n
21.mを2で割ったn次方
m >> n
22.整数kを求めてx位(高い)からy位(低い)の間に何個の1があります
public static int findChessNum(int x, int y, int k) {
int result = 0;
for (int i = y; i <= x; i++) {
result += ((k >> (i - 1)) & 1);
}
return result;
}
23.絶対値をとる
int abs(int n){
return (n ^ (n >> 31)) - (n >> 31);
}
/* n>>31 n , n ,n>>31 0, n ,n>>31 -1
n n^0=0, , n n^-1 n -1 , , n n 1, -1 */
24.1回の数値のみが空でない整数配列を与え、ある要素が1回しか現れない以外は、各要素が2回現れる.それが一度しか現れなかった要素を見つけます.説明:あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?例1:
: [2,2,1] : 1
例2:
: [4,1,2,1,2] : 4
この問題でまず思いついたのは異或の特性だ.同じ数字の異和の結果が0であれば、奇数回現れるのは最後に私たちが望んだ結果に違いない.
public int singleNum(int[] nums){
int res = num[0];
for(int i=1;i
まとめ
機能
例
ビット演算
最下位を外す
(101101->10110)
x >> 1
最後に0を追加
(101101->1011010)
x << 1
最後に1を追加
(101101->1011011)
x << 1+1
最下位を1にする
(101100->101101)
x | 1
最下位を0にする
(101101->101100)
x | 1-1
最後の取反
(101101->101100)
x ^ 1
右からk位を1にする
(101001->101101,k=3)
x | (1 << (k-1))
右からk位を0にする
(101101->101001,k=3)
x & ~ (1 << (k-1))
右からk番目の位置を逆にする
(101001->101101,k=3)
x ^ (1 << (k-1))
末尾3位をとる
(1101101->101)
x & 7
末k位をとる
(1101101->1101,k=5)
x & ((1 << k)-1)
右からk位をとる
(1101101->1,k=4)
x >> (k-1) & 1
末k位を1にする
(101001->101111,k=4)
x | (1 << k-1)
末k位取反
(101001->100110,k=4)
x ^ (1 << k-1)
右の連続する1を0にする
(100101111->100100000)
x & (x+1)
右から1番目の0を1にする
(100101111->100111111)
x | (x+1)
右の連続する0を1にする
(11011000->11011111)
x | (x-1)
右の連続する1をとる
(100101111->1111)
(x ^ (x+1)) >> 1
右から1番目の左を外す
(100101000->1000)
x & (x ^ (x-1))
判定奇数
(x&1)==1
けっていぐうすう
(x&1)==0
クリックして詳細を表示