8000 Update src/algebra/bit-manipulation.md · cp-algorithms/cp-algorithms@4c7220a · GitHub
[go: up one dir, main page]

Skip to content 8000

Commit 4c7220a

Browse files
Update src/algebra/bit-manipulation.md
Co-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
1 parent 7adbf1c commit 4c7220a

File tree

1 file changed

+1
-0
lines changed

1 file changed

+1
-0
lines changed

src/algebra/bit-manipulation.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -205,6 +205,7 @@ We can use the fact that for numbers upto $2^x$ (i.e. from $1$ to $2^x - 1$) the
205205
We can see that the all the columns except the leftmost have $4$ (i.e. $2^2$) set bits each, i.e. upto the number $2^3 - 1$, the number of set bits is $3*(2^{3-1})$.
206206
207207
With the new knowledge in hand we can come up with the following algorithm:
208+
208209
- Find the highest power of $2$ that is lesser than or equal to the given number. Let this number be $x$.
209210
- Calculate the number of set bits from $1$ to $2^x - 1$ by using the formua $x*(2^{x-1})$.
210211

0 commit comments

Comments
 (0)
0