2019-06-01 02:44:19 (edited by goran 2019-06-01 02:51:18)

Hi
I have recently started learning c, and it seems to be a fun experience so far, especially since you can't run out of learning resources easily.
There is one subject however, that have me stuck at the moment, which is bitwise operators. It took me a while to start getting the hang of how they work exactly. Now that i have a basic understanding of those operators, i'm wondering what are their uses. I mean, I have read many tutorials on them. They all say that those operators work on the individual bits of integers and such, but I have yet to find one that mentions their  everyday use. So what are the practical uses of those bitwise operators? Are their any situations in which a developer actually needs to use them?
thanks in advance for any help.

2019-06-01 03:53:16

It depends. On some architectures bitwise operations can be more efficient, though again it depends. So, basically a way to optimize performance.

-BrushTone v1.3.3: Accessible Paint Tool
-AudiMesh3D v1.0.0: Accessible 3D Model Viewer

2019-06-01 04:56:18

Yes, there are many uses for them. For example, you can use bitwise operators to add, multiply, subtract, and divide numbers. This saves on CPU cycles, and it's an efficient way to represent data without using multiple integers. I should clarify that as the name suggests, bitwise operators operate on the level of bits (binary digits). So, building truth tables and practicing with 32-bit integers is always helpful in understanding how to manipulate data using this method. If you know what you're doing, you can use them to write simple conditionals involving numbers by eliminating checks altogether and self-evaluate for flags. These things are especially used in embedded systems in where you have a microcontroller with limited memory and you want to optimize performance and reduce footprint. If you study assembly languages, some of this might make more sense. I've worked on embedded systems before, and believe me, if you know how to use bitwise operators and other features of C (unions, bit structs, etc), you will be greatly valued.

2019-06-01 15:36:47

If you need more than 4 booleans in a class, struct, or whatever, it's easier to use an int, using the bitwise operators to interact with the bits. This is also helpful when you don't know in advance how many boolean flags you'll need.
There are some other uses you might come across in game-related libraries, related to efficiently storing data for collisions, or complex properties that can't be reduced to booleans. If I remember correctly, Box2d has two ints for specifying arbitrary custom types for objects. I forget the exact rules, but iirc it's something like only let the objects interact if x.mask1 & y.mask2 is nonzero. This let's you be as complex or simple as you want for a wide variety of projects.

Things I use bitwise operations for all the time:
- I had a class for input configurations (keyboard, joystick, whatever) that assumed something like your typical game controller, with 6-12 buttons. Using bits for this allowed me to use the same constants for controls and movelists.
- Movelists. Since many of my games do some fighting game-like movelists, I use ints to define what state the characters are in, and bits to map those to commands. You could just use something string-based, but somehow this has worked much better for me.
- Lists of properties that could change later. Continuing with the fighting example, a move might involve fire, might use a common set of battlecries, might need to track the sound or not, might be unstunnable, unblockable, cancelable, seeking, weightless, etc, etc. As the game develops, some new properties might become necessary or useful. A giant pile of booleans isn't just inefficient for the machine; it's a time-waster, confusing to navigate, takes up space in your code that affects readability, and if you do things like by-hand cloning or serialization, you'd have to change that every time you add or modify a property. On the other hand, you can just declare "int flags;", and all you need to do is add constants (if you don't just memorize the values, but who does that?).
- Unlockables or variable lists of playable characters. I'll use EC as an example. Each level has a certain list of characters who can be used in that level, and sometimes that list changes. An array or linked list might be viable, but I was getting the list only when needed, so just returning an int was simpler.
- Voxels. I don't have the patience to make a new map editor for every game that requires a different format, so whenever I can just make the map into an array of strings, or at least load from one, that's preferred. That does limit what I can do in terms of 3d, though. One solution for this is to map an int to each unique char on the map, and have that int represent the vertical stack. This lets me make maps with a notetaker whereever I happen to be at the time, without being restricted to 2 dimentions.
- Aiui, mainstream games have used bitmasks to speed up hit detection. Kinda irrelevant if you're using a super optimized physics engine on a super optimized machine, but that's a thing.
- Efficiency, if you have memory limits. You'd be surprised how much you can fit into 8 bits.
- Some libraries do things like represent colors as a single int. Swamp maps do this. If you work with these, you'd need to use bitwise operators to work with red/green/blue individually.

看過來!
"If you want utopia but reality gives you Lovecraft, you don't give up, you carve your utopia out of the corpses of dead gods."
MaxAngor wrote:
    George... Don't do that.

2019-06-02 02:05:32

Thanks guys! I was actually about to abandon this concept for now as it was a bit more complicated than what I have worked with so far, since I had no idea about its use and that gave me little incentive to bother with it. Although some of what you guys have wrote are too advanced for me at this stage to make complete sense of, but at the same time, you have given me a lot of things to look up, take note of for later, and/or look forward to smile .
A couple more questions (I have a feeling that they will be far from my last questions):
kaigoku mentioned truth tables to work with for  practicing  the use of those operators, and I have seen other people refer to them as well while explaining logical operations and such. I have tried to look it up, but I haven't been able to grasp the making of it so far, not sure if it's because of the inaccessibility of the way they are represented, or i'm to blame myself sad . So is there any specific resource or way with which the construction of truth tables can be made/learned easier?

also, Could you refer me to or give me a very simple practical example of how the bitwise operators can be used to do arithmetic operations or any other operation which is easy to understand for a newbie? Code example I mean.
Thanks again for bearing with my noob questions smile

2019-06-02 02:13:41

I suppose this might be a dumb question, but are you familiar with binary? You'll need to know it in order to grasp bitwise operations.

What game will hadi.gsf want to play next?

2019-06-02 02:20:41 (edited by goran 2019-06-02 02:37:59)

fundamental question actually I suppose smile
i'm familiar with binary as well as what each operator does. I mean how & returns the bits that are true in both operands, how | | returns the bits that are true in one of the 2 given operands and so on, I just fail to figure out how to use them to accomplish something useful LOL.

2019-06-02 06:41:04

I used bitwise in C++ once for a maze generation system. Instead of having lots of boolean values (thereby wasting precious memory) I used a single 32-bit integer (or was it 64) to represent all the flags for each cell. For example, I used something like if ((cell.flags&Door)==1) to test if it was a door and so on. That same integer also held directional flags as well, so it was used for quite a lot of things. To add a flag, I used the &= operator, which is identical to doing cell.flags = cell.flags & flag. For removing bits/flag negation, I used the &= operator combined with the ~ operator, making it cell.flags&=~flag. A good way of describing bit shifts is to imagine your bits as an infinite stream of ones and zeros. This infinite stream is your programs address space, since bitwise operations can happen anywhere in the address space (and if your writing an OS driver or kernel, it can happen *anywhere*). If you bit shift to the left (x<<y), you are shifting the x-bit to the left by y positions; i.e.: the y-bit becomes the x-bit. Similarly, if you bit shift to the right (x>>y), the x-bit becomes the y-bit, the exact opposite of the bit shift to the left. (Please correct me if I am wrong; I'm attempting to paraphrase this topic when I was reading low-level assembly language documentation on developing OS kernels -- I tried and failed at that, BTW. Always triple-faulted, and I could never find out why, since my kernel (which I only wanted to print "hello world") didn't support serial ports. Perhaps I should try that again sometime.)

"On two occasions I have been asked [by members of Parliament!]: 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out ?' I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question."    — Charles Babbage.
My Github

2019-06-02 14:22:13 (edited by kaigoku 2019-06-02 14:26:07)

Post 5, truth tables can be expressed as regular row-column tables. I think Wikipedia has a nice entry on truth tables you can read. On the web, they can usually be represented in standard HTML tables. These are simple tables that have headers such as, x, y, x&y, x|y, x^y, etc. Then, for each row, you have the different combination of bits that x and y can take on. I would show you an example, but not sure if you can make tables in BB code or whatever this forum system uses. That, and I am kinda in a hurry. lol A quick example of using bitwise operators to do arithmetic is by using AND operator on bits for carry bit, and XOR on the two bits to add, shift left 1 position to the left, and add. There is a very interesting implementation here: https://www.geeksforgeeks.org/add-two-n … operators/ . It uses a recursive technique, which is not very efficient, but it gets the point across. Also, a good article to read on Wikipedia is on the adder circuit. Keep in mind that at a circuit level, the ALU only has logic gates available to it. A good intro to digital logic or computer architecture might be really useful. Hope some of this is helpful and it doesn't go over your head. Users of higher-level programming languages don't usually have to concern themselves with these things, but bitwise operations and registers and all that fun stuff is essential to how programming languages can do what they do so easily. If you take a computer science cirriculum, much of this is covered in an Intro to Digital Logic course, or Computer Organization course. And the real fun stuff is if you dive into Electrical Engineering and you get to play with FPGAs and microprocessors, not to be confused with microcontrollers.

2019-06-02 14:51:56 (edited by goran 2019-06-02 15:09:39)

Thanks a lot kaigoku, i'l check those things out and will see smile

problem is, I live in a country where blind people don't study math at all beyond very basic stuff such as addition and subtraction, much less other sciences. So probably this is partly why I have dificulty with those advanced concepts, and i'l have a long road ahead of me if I continue.

I have worked with higher level programming languages before, but i'd rather understand what's going on behind the scenes than doing things the easy way, unaware of how do things work exactly, even if it means spending long periods of time trying to make sense of things.

2019-06-02 17:06:51

ok I think I grasped the setting and removing of flags, but just to be sure that it's the correct way, let's post it here smile

#include<stdio.h>
#include<string.h>
int music, state=1;
void toggle(char option[10])
{
if (option=="playing")
{
music^=state;
}
else if(option=="repeat")
{
music^=state<<1;
}
}

also, is there any difference between these 2 statements?

music^=state<<1;

music^=state*2;

2019-06-02 18:19:31

I think truth tables are more annoying than helpful in audio, and just each case as a statement would be easier to follow.

No, there is no difference between those two statements. smile Bitshifting is more useful when the power of 2 in question is variable. It's faster and easier to type x<<y than x * power(2, y). Python does have exponents (x * (2 ** y)), which is still worse than x<<y, but not as much. And bitwise operations are faster on hardware, but that's not necessarily true for higher level languages that might be optimized away from them.

看過來!
"If you want utopia but reality gives you Lovecraft, you don't give up, you carve your utopia out of the corpses of dead gods."
MaxAngor wrote:
    George... Don't do that.

2019-06-04 15:45:01 (edited by r3dux 2019-06-04 15:47:11)

TL:DR - Don't optimise via bitfields, let the compiler and the computer do its job.

Sometimes bitfields are of use (i.e. simple powers of 2, some if-this-then-that cases), but the vast majority of the time they make a simple task more complicated, the code becomes significantly harder to understand (and hence modify and debug) - and as such they are very prone to bite you in the ass.

If you want a book on bit-twiddling (and this is one I actually own), try:
http://www.hackersdelight.org/

I'd caution anyone thinking they can save a few cycles by raw bit manipulation that they may also cost themselves a few hours if not days or weeks later down the track figuring where their bit-twiddling didn't work as expected in corner-cases because they bypassed the normal checks-and-balances built into the programming language primitives they were working with.

Also, only ever optimise the core code than runs 95% of the time. If you can make something 1ms quicker and it runs 60 times per second then you're up 60ms * 60 minutes * 24 hours = 86,400ms = 1,440 seconds = 24 minutes per day. If you optimise something by 5000ms (5000 times more!) that runs once per day then you gain 5 seconds, and you probably spent at least a few hours 'optimising' it.

2019-06-04 16:16:01

Post 12 and 13, you make valid points in that perhaps it is not worth optimizing using bit manipulation if you have a nice compiler that will do everything for you behind the scenes. Especially since most of the bit manipulation operators are abstracted away from machine-level implementations due to overhead, register allocation, etc. However, it's obvious that OP is just curious about how these things can be applied. It never hurts to be curious. smile I will say, OP, just keep that in mind when you want to use bit manipulation in higher level programs you decide to write that it might not be worth the headache. These are definitely tricks that an embedded systems engineer could use to significantly improve certain aspects of a program. Even at that, sometimes, there are compilers for really well-known microcontrollers, and if you have the privilege of having a nice OS, then you might not even have to touch them in any case. Bit manipulation certainly facilitates a better understanding of computers at a much lower level. IMO, a nice intro to Electrical Engineering. smile

2019-06-04 16:53:55 (edited by r3dux 2019-06-04 16:54:18)

@kaigoku - Entirely agree with you, and curiosity is king - which is why I included a reference to a great book on a variety of methods to go about 'bit-twiddling' if that's something of interest smile

2019-06-05 08:41:22 (edited by pranam 2019-06-05 08:42:11)

Hi,
I'm also learning C but I haven't encountered bitwise operators. I will look on the subject. Are they of any use other than shifting and formatting your output?

Best regards
Pranam
Don't forget to give me a thumbs up!

2019-06-05 15:51:29

@16, yep. They're useful for packing a ton of flags into a single variable, which is a very nice thing. https://stackoverflow.com/questions/209 … -operators

"On two occasions I have been asked [by members of Parliament!]: 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out ?' I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question."    — Charles Babbage.
My Github