contributed by JoshuaLee032190
next_pow2
,我們可以知道這個題目要找出當前整數的下一個2 的冪整數。uint64_t next_pow2(uint64_t x)
{
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> AAAA;
x |= x >> 16;
x |= x >> BBBB;
return CCCC;
}
x |= x >> 1
,而且AAAA
的下一行為 16,由此我們可以推測 AAAA
為 8BBBB
為 32CCCC
就要從前面想了,前面的意思為把這個整數的某一個位元往右全部填滿 1,那在全部都是1的狀況,我們只需要 + 1
即可得出最終的結果我覺得前面右移做了七次有點多此一舉,而測試後,其實可以把code 改成以下的狀況達到同樣的結果
uint64_t next_pow2(uint64_t x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return x + 1;
}
int __builtin_clz (unsigned int x)
// Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
int __builtin_clzl (unsigned long)
// Similar to __builtin_clz, except the argument type is unsigned long.
// 利用 __builtin_clzl 改寫完成
uint64_t next_pow2_2(uint64_t x)
{
int hi = __builtin_clzl(x >> 32);
int lo = __builtin_clzl(x);
uint64_t res = 1;
return (hi == 31) ? res << 31 - lo + 1 : res << 64 - hi;
}
grep -r "roundup" *
找出了 pci.h# /include/linux/pci.h
static inline int pci_rebar_bytes_to_size(u64 bytes)
{
bytes = roundup_pow_of_two(bytes);
/* Return BAR size as defined in the resizable BAR specification */
return max(ilog2(bytes), 20) - 20;
}
20
的數字代表了 1mb 的大小所以先取 max
提示: 可執行 gcc -O2 -std=c99 -S next_pow2.c 並觀察產生的 > next_pow2.s 檔案,確認 bsrq 指令 (表示 “Bit Scan Reverse”)
next_pow2_2:
.LFB14:
.cfi_startproc
endbr64
shrq $32, %rdi
movl $64, %ecx
movl $1, %eax
bsrq %rdi, %rdi
xorq $63, %rdi
subl %edi, %ecx
salq %cl, %rax
ret
.cfi_endproc
輸入
,的二進位連接起來的數字int concatenatedBinary(int n)
{
const int M = 1e9 + 7;
int len = 0; /* the bit length to be shifted */
/* use long here as it potentially could overflow for int */
long ans = 0;
for (int i = 1; i <= n; i++) {
/* removing the rightmost set bit
* e.g. 100100 -> 100000
* 000001 -> 000000
* 000000 -> 000000
* after removal, if it is 0, then it means it is power of 2
* as all power of 2 only contains 1 set bit
* if it is power of 2, we increase the bit length
*/
if (!(DDDD))
len++;
ans = (i | (EEEE)) % M;
}
return ans;
}
ans = (i | (EEEE)) & M
可知,len
為往左移動的距離len
才會需要 + 1
,此情況為:# 考慮 1 - 10 的位元如下
1 : 0001
2 : 0010
3 : 0011
4 : 0100
5 : 0101
6 : 0110
7 : 0111
8 : 1000
9 : 1001
10: 1010
AND
運算得到 0 的狀況DDDD
很明顯就是 i & (i - 1)ans
中,可想而知 EEEE
為 ans << len
,如此一來就可以把運算後的數字放入當前空下來的位元int concatenatedBinary(int n)
{
const int M = 1e9 + 7;
int len = 0;
long ans = 0;
for (int i = 1; i <= n; i++) {
len = 32 - __builtin_clz(i);
ans = (i | (ans << len)) % M;
}
return ans;
}
is_pattern
主要是在看輸入的無號整數的編碼是否存在特定樣式1000000000000000
做and,當位元還沒有被清空時,只要中間的連續1斷開則回傳false
後面的function 則是找出這個pattern 會發生的事情
# 我們來看一下這個 pattern (這個假設在 bit數為5的狀況)
10000
11000
11100
11110
11111
首先,題目很明顯告訴你有一個 xor 跟比大小;也就是我們必須往比大小的方向思考
那要怎麼樣才可以利用這個 pattern 比大小呢?
我們只需要先取 x 的負數,如此一來可以得到
10000 ==> 10000
11000 ==> 01000
11100 ==> 00100
11110 ==> 00010
11111 ==> 00001
此時 x ^ -x 就會變成
00000
10000
11000
11100
11110
最後再與原本的狀況比大小,此時,如果符合這個 pattern 的話,結果一定會比原本的輸入還要小,此時只要比大小,回傳即可。
EEEE
為 -x
FFFF
為 x
or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing