contributed by < ShallowFeather
>
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;
}
AAAA 為 8
BBBB 為 32
CCCC 為 x + 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;
}
可以這樣運算是因為可以知道當右移一位並做 |
運算後會將他的右項倍增
就像是
1000000 在跟 0100000 |
後會是 1100000
也因此可以直接將下一次運算時直接右移 2 位來節省運算次數。
以此類推。
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;
}
DDDD 為 i & (i - 1)
EEEE 為 ans << len
i & (i - 1)
此操作將會移除最右邊的那個 1
那如果說他是 2
的冪次方就需要多一個 bit
來存他的二進位數值,因此將 len++
並在後面左移 len 位數並將 i
附加在 ans
右側
bool is_pattern(uint16_t x)
{
const uint16_t n = EEEE;
return (n ^ x) < FFFF;
}
EEEE = -x
FFFF = x
此題目要求為 確認 x 的 binary 是否符合在最右邊的 1
後皆為 0
-x 為 x 的二補數
EX:
如 x = 1100 0000 0000 0000 則他的補數為 0100 0000 0000 0000
因此並不會比 x 還要大
不過如果 x 為 1100 0000 0000 0001 其補數則為 0011 1111 1111 1111
則必定大於 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