算法笔记

//把你传进来的容量 cap，调整成“大于等于 cap 的最小 2 的幂”  
static final int tableSizeFor(int cap) {  
    int n = cap - 1;  //当 `cap` 本身已经是 2 的幂时，结果还能保持原值, 16->32
    n |= n >>> 1;  
    n |= n >>> 2;  
    n |= n >>> 4;  
    n |= n >>> 8;  
    n |= n >>> 16;  
  
    // 先判断当前条件是否成立，成立才走这个分支。  
    if (n < 0) {  
        return 1;  
    }  
    return n >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : n + 1;  
}
  10000000
| 01000000
= 11000000

  11000000
| 00110000
= 11110000

  11110000
| 00001111
= 11111111

public boolean bin(int[] arr, int tar){  
	int l = 0, r = arr.length - 1;  
	while(l <= r){  
	int mid = l + (r - l) / 2;  
	if(arr[mid] < tar){  
		l = mid + 1;  
		}else if(arr[mid] > tar){  
		r = mid - 1;  
	}else{  
		return true;  
		}  
	}  
return false;  
}

pre[0]=0;
pre[1]=arr[0]+pre[0];
pre[2]=arr[1]+pre[1];
pre[i]=arr[i-1]+pre[i-1];//i->[1,arr.length]

//sum[l-r]
gap=pre[l+1]-pre[r];