DEV Community

Cover image for "The Power of Bit Manipulation: How to Solve Problems Efficiently"

"The Power of Bit Manipulation: How to Solve Problems Efficiently"

Anurag Verma on December 28, 2022

There are a few key topics that are important to understand when it comes to bit manipulation in competitive programming: Bitwise operations: It ...
Collapse
 
cicirello profile image
Vincent A. Cicirello

You don't want to use the 3 xor swap trick. It is clever, but that is it. If you measure, you'll see it is slower than just using temp variable and 3 assignment statements. And it is less readable. So you sacrifice readability without gaining anything.

Collapse
 
anurag629 profile image
Anurag Verma

I am not sure but it will faster in other programming language😊.

Collapse
 
cicirello profile image
Vincent A. Cicirello

No, it won't be. I've measured specifically in Java. But it should be slower regardless of language. You essentially have 3 xors, plus 3 assignments for the xor trick. The more straightforward way is just 3 assignments plus declaration of temp variable. The 3 xors will be slower than the variable declaration.

Thread Thread
 
anurag629 profile image
Anurag Verma • Edited

Ohhh i missed it. I think i should take rest from bit manipulation as i messed up these things πŸ™„πŸ€―πŸ€―πŸ˜‡

How i can do this..... πŸ˜’πŸ˜’πŸ€¬πŸ€¬

Collapse
 
cicirello profile image
Vincent A. Cicirello • Edited

Good list of bit manipulation operations.

A good book for more bit manipulation is:

Hacker's Delight is a software algorithm book by Henry S. Warren, Jr. first published in 2002. It presents fast bit-level and low-level arithmetic algorithms for common tasks such as counting bits or improving speed of division by using multiplication.

It has some some of the tricks from your post and faster versions of others. For example, you can count 1-bits without a loop. Plus many more.

Collapse
 
anurag629 profile image
Anurag Verma

Thanks @cicirello for book I will go through this book and update this post as early as possible.

Collapse
 
cicirello profile image
Vincent A. Cicirello

Another way of isolating right most bit:

y = x & 1
Enter fullscreen mode Exit fullscreen mode
Collapse
 
anurag629 profile image
Anurag Verma

YES 😊.😊.

Collapse
 
bhagatharsh profile image
BhagatHarsh

Great read, brushed up my old bit manipulation skills😁.

Collapse
 
anurag629 profile image
Anurag Verma

Thanks @bhagatharsh Follow me for such more content.

Collapse
 
dinifarb profile image
DiniFarb

Thanks, I really enjoyed reading this article 😊

Collapse
 
anikethsdeshpande profile image
Aniketh Deshpande

Very nice list of tricks!

Collapse
 
anurag629 profile image
Anurag Verma

Thanks

Collapse
 
avtozavodetz profile image
avtozavodetz • Edited

Thanks for the useful article!
But it looks like gcd example has some mistake: it returns None, and % should be used instead of &.

Collapse
 
anurag629 profile image
Anurag Verma

Thanks @avtozavodetz for correction.

Collapse
 
v69 profile image
Alex

'Bitonic sort' is broken and doesn't work as expected.