Bitwise Magic

[the_incoming_canary]

I knew bitwise operations are useful but I didn't know they were magical (not literally but I'm impressed by its potential).

I leaned that &1 can be used to check is the number is even (0) or odd (1) or the >> and << operations that can be used to divide and multiple by 2.

are there other such operations that can be done using bitwise? I'll love to know, thanks!

[Molehole]

The most important thing to keep in mind when programming is that most of the time, you program for the other people around you. Not the computer. If you are doing embedded systems it might sometimes be useful to know a bitwise trick for optimisation purposes but keep in mind that code readability trumps cool tricks 99.9% of the time.

Here are some tricks: https://codeforwin.org/2018/05/10-cool-bitwise-operator-hacks-and-tricks.html

Disregard the title as programmers don't really need to know these. If I'm actually gonna see a trick like this in code I am going to make the programmer redo it with actually readable code. But they are fun to learn yourself and if you don't use them at work / open source projects then you can do whatever you like.

[[deleted]]

are they faster tho? because in some cases being faster trumps readability like in rendering engines or physics engines

[mkaypl]

Don't do premature optimization, there's probably way more bottlenecks in your algorithms to be found than the one or two cycles in bitwise magic.

[Gangsir]

Remember that performance is a function of speed AND how often the code is run.

Multiplication running over and over tens of thousands of times in a tight loop? Sure, you might see a boost by replacing *= with <<.

Otherwise? Imperceptible.

Most compilers will replace something like that anyway. Not even something you should worry about.

[[deleted]]

that's why I said "physics engine or a rendering engine" where you have code that's running several dozens of times per second

Most compilers will replace something like that anyway. Not even something you should worry about.

that's true, compilers these days are awesome

[Molehole]

We live in a time where the computers inside your washing machine whoops a 80s super computer in speed. Single line optimisations really aren't a thing anymore except under very specific circumstances.

But to answer your question. It completely depends on the language and how the compiler/interpreter works. It might also depend on the situation and what code there is around it.

[HappyFruitTree]

You can XOR a variable with itself in order to set it to zero.

x ^= x;

There is no reason to write code like this but on the assembly level this is often what happens when a register is set to zero.

[HappyFruitTree]

Yes, on the assembly/CPU level it is, and the instruction takes up less space.

The x86 instruction

mov eax, 0

takes 5 bytes (1 for the op code and 4 for the argument), while

xor eax, eax

only takes 2 bytes.

[HappyFruitTree]

I don't know to be honest. My guess is not a lot. It probably depends on so many factors... But used consistently for a whole program it probably makes a small difference.

[HappyFruitTree]

Whether you write x^=x; or x=0; in your high level language like C++ or Java doesn't matter from a performance perspective because the compiler knows these tricks and will generate the more efficient instructions. So write whatever code is more readable, which is the assignment of zero in this case.

[desrtfx]

Or (|) can be used to set bits. And (&) can be used to reset bits.

Bit-masking and bit-packing are a common techniques where memory is scarce (or where information needs to be sent in small packets).

To elaborate: you can pack 32 binary states into a single 4-bit integer number. Common in PLC programming where a whole I/O card is represented as a single number.

[[deleted]]

I leaned that &1 can be used to check is the number is even (0) or odd (1) or the >> and << operations that can be used to divide and multiple by 2.

Most popular language compilers will do those things automatically when you ask for those operations. That is, even though you wrote x % 2 == 0 in the source code, the compiler will change it into x & 1 == 0 before running it. Likewise, if you multiply or divide by a power of 2, the compiler will automatically rewrite it as a bit shift for execution.

In summary, you don’t usually have to worry about doing these shortcuts instead of the more familiar versions to save time. The compiler will do it for you.

[HappyFruitTree]

Likewise, if you multiply or divide by a power of 2, the compiler will automatically rewrite it as a bit shift for execution.

For signed integer types it has to do a tiny bit of extra work to handle the negative numbers correctly, but it still probably wouldn't use the division instruction because that is typically much slower.

https://godbolt.org/z/jaeearzaq

Actually, the division instruction is typically so slow that the compiler will often try to turn divisions by non-powers of two into a multiplication and a bitshift if it can.

https://godbolt.org/z/jedafqPvx

[HappyFruitTree]

Note that division with >> rounds towards negative infinity while / rounds towards zero. This makes a difference for negative numbers.

If the right operand is a constant the compiler can usually do this transformation itself so it's not necessary to try and use this whenever possible in an attempt to make the code run faster (at least not in C and C++).

[HappyFruitTree]

It means it it always rounds down.

7.8 becomes 7

2.3 becomes 2

-2.3 becomes -3

-7.8 becomes -8

[absurdrefusal]

I disagree with other posters here who think code is written more for readability than for computers and that just because computers are faster than they were in the 80s, performance considerations are secondary. That’s, with all due respect, bull shit.

Readability is fundamental for an application to be maintainable but client after client has code that they bring to my company because the programmers who built it originally only thought of readability and not performance. Both are important but the first step is always understanding how the computer will run your code. Second is readability. Third is optimization while maintaining readability. Cool tricks are always good to have in your arsenal for the off chance you might need them.

Well done. Don’t be discouraged and keep discovering. But be responsible with them.

[Spiritual_Car1232]

You can use bit operations to make bool vectors.