public class Test1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = {15,16,17};
//2^3 = 8
//001 1
//010 2
//011 3
//100 4
//101 5
//110 6
//111 7
//000 0
for(int s=1;s<(1<<array.length);s++) {
for (int j = 0; j < array.length;j++) {
if ( (s & (1<<j)) > 0) {
System.out.print(array[j]+" ");
}
}
System.out.println();
}
}
}
比插入排序快 最少跟插入排序一樣
因為 interval最後會變為1 這時就是插入排序了
會比插入排序快的因為
希爾排序先兩兩處裡了一些順序
interval為1時作插入排序所以可減省插入排序的時間
可以看成再插入排序前先整了一番順序
可參考此影片
int arr2[7] = {16,51,63,1,25,70,15};
int len = 7;
//習慣間隔是陣列長度除2 len >>1 表示除2
for (int interval=len>>1;interval > 0;interval>>=1){
for (int k = interval;k < len;k++){
int target =arr2[k];
int x = k - interval;//取得左邊與k差為interval的區間
while(x > -1 && arr2[x] > target){
arr2[x+interval] = arr2[x];
x-=interval;
}
arr2[x+interval] =target;
}
}
//java 可換成foreach 輪巡陣列
for (auto v : arr2){
cout << v << ' ';
}
將二進位的當中為1的偶數與奇數位置交換
/例如:
// 9 = 1001
// 3 2 1 0
// 1 0 0 1
//3 與 2交換
//1 與 0交換
//變為 0 1 1 0 = 6
//快速作法
//1 取偶數位 手動產生一組01010101...的數值 因為1在偶數位
//所以做&可以取得偶數位的1
//2 取奇數位 手動產生一組10101010...的數值 因為1在奇數位的1
//所以做&可以取得奇數位的1
//3 將步驟1的偶數位 向左偏移一格 就變為奇數位了
//4 將步驟2的奇數位 向右偏移一格 就變為偶數位了
//ex
// 1 0 0 1 9
// 0 1 0 1
//&======================
//0 0 0 1 偶數位
// 1 0 0 1 9
// 1 0 1 0
//&======================
//1 0 0 0 奇數位
// 0 0 0 1 << 1 = 0010
// 1 0 0 0 >> 1 = 0100
//5 將步驟3與步驟4的 做xor就可合併 因該也可以做or合併吧
// 0010 ^ 0100 = 0110
int n3 = 9;
int mask1 = 0x555555;//0101 正好是16進位的5
int mask2 = 0xaaaaaa;//1010 正好是16進位的a(10)
cout << ((n3 & mask1)<<1 ^ (n3 & mask2)>>1);
正整數N的二進位有多少個1
//假設N為9
//作法1 找出 N&1 << i 等於 1 << i的個數
//約要跑31次 第32位是正負符號
int n = 9;//二進位為1001
int count = 0;
for (int i = 0;i <32;i++){
if ((n & i << 1) == i << 1){
count++;
}
}
cout << count <<'\n';
//作法2 利用減法特性
// 此題來說跑2次 效能較好
//假設N=9二進位為1001
//1001 -1 = 1000 將 1001 & 1000 會變為1000
//1000 -1 = 0111 因為0不夠減1所以要向右邊借2所以 減後答案為0111
//將1000 & 0111 結果為 0 這就是結束點
//原始數值定義為N 差定義為D
//每次減完都會將最靠近右方的1變為0
//D&N 正好可以消除靠近右方的1
//例如:1000 -1 = 0111
// 1000 & 0111 = 0000
//此方法其實是在計算消除多少次1
int n2 = 9;
int count2 =0;
while(n2){
count2++;
int d = n2 -1;
n2 = n2 & d;
}
cout <<count2 <<'\n';
例題假設陣列內只有一個重複的元素幫我找出來
int a[6] = {1,2,3,5,4,5};
int x = 0,ans=0;
for (int i = 1;i<=5;i++){
x ^= i;//產生一組所有數字的xor
}
for (int i = 0;i <6;i++){
ans =a[i]^x; //去除重複的xor
x = ans;
}
cout << ans;
Swap(交換變數) int a = 10;
int b = 20;
int x = a ^ b;
a = x ^ a;
b = x ^ b;
cout << a << b;陣列當中只有一組不兩兩重複 請找出不兩重複的數值 int v[11] = {1,1,2,2,3,4,4,5,5,6,6};
int m = 0;
for(int i = 0;i < 11;i++){
m ^=v[i] ;
}
cout << m << '\n';