I have been reading up on some of this material and I keep finding myself asking the same question over and over, "What is bit shifting / manipulation used for"? I just don't understand where you would use it.
Thanks,
--Joe
I have been reading up on some of this material and I keep finding myself asking the same question over and over, "What is bit shifting / manipulation used for"? I just don't understand where you would use it.
Thanks,
--Joe
Cryptography often involves what's called 'bit-shuffling', which is needed to achieve a diffuse hash.
Many compression algorithms work by performing a transformation of 1 Byte -> N bits, and have to basically write to a file 1 bit at a time.
Many file formats pack much information into bits. For example, a 4-color .png file represents each pixel as 2 bits, with 4 pixels per byte. To write each pixel you need bit manipulation.
Callou collei we'll code the way
Of prime numbers and pings!
some data streams like networking are defined on the bit level, so you'd need to be able to access that.
Thanks guys for getting back to me so quickly, I think I understand them now.
There are many different uses for bitshifts. The most common is divide/multiply by powers of 2The same obviously applies for multiplication.Code:x >> 1; // x / 2 x >> 2; // x / 4 x >> 3; // x / 8 ... x >> 15; // x / 32768
Now, the compiler will most likely translate a "x *4" to "x << 2" automatically for you, so it's really not that much to gain from writing code like that.
If you have hardware that delivers data in certain registers, you may want to pick out "bit 7..4" out of a register, so you shift it down by 4 ( x >> 4 ) to make it bits "3..0" instead - because it's easier to understand/deal with a number 0..15, rather than the numbers 0..240 with gaps of 16 between.
Really, it's just a way to describe in C something that can be done in assembler, and low-level code such as drivers need to be able to do these things. Since writing drivers in C is a neat thing to be able to do (I wouldn't want to write a proper driver in assembler these days, with all the complexity in modern hardware). So it's handy to have those for that purpose.
There are other uses as well, some of which have been mentioned above. Really, it's all about handling numbers as a sequence of bits that you can "shuffle about".
--
Mats
Really, you can do an awful lot of programming without ever worrying about bits & bytes...
It's mostly used when you are programming for the hardware level. If you are writing firmware or drivers you are very likely to be doing lots of bit-operations.
Like matsp said, you are often treating the variable as a binary "bit-pattern", rather than a "number." I think this is a big source of confusion for beginning programmers... Bitwise manipulation done on decimal numbers...
In a real-world program, one particular bit (in a register) might represent the on/off state of a switch, or one bit might drive an LED. You need to read/test the individual bit to determine the on/off state of the switch, and you need to manipulate one particular bit (at a particular address) to turn the LED on/off.
In C/C++ these bit patterns are usually represented in hexadecimal. You will rarely see bitwise operations used with decimal numbers*. This is because it's very easy to convert between binary and hex (much easier than converting between binary and decimal). And, you can't really use binary directly in a C/C++ program... And, you wouldn't want to, because once you get beyond 8-bits, binary numbers get difficult to read, write, or speak. (There are ways to accept binary input and/or display binary output, but these are not built into cin or cout.)
We use bitwise operations and bit-testing quite a bit when troubleshooting hardware. We can read/write data patterns to check for bad bits or data lines.
It's very common to do a quick test by writing patterns like 0000h, FFFFh, 5555h, and AAAAh to memory (or a register) and then reading them back. And, we can look at a data line (or address line) with a "scope" (oscilloscope) to see if it's 1, 0, or toggling.
0000 hex = 0000 0000 0000 0000 binary
FFFF hex = 1111 1111 1111 1111 binary
5555 hex = 0101 0101 0101 0101 binary
AAAA hex = 1010 1010 1010 1010 binary
* Of course, the computer doesn't know or care if these are "decimal numbers". They are all stored in binary.
Last edited by DougDbug; 08-07-2007 at 07:30 PM.
"interfacing with hardware" is a pretty bad case for using bit shifts. Bit fields were already created to handle that problem and represent it a lot more cleanly.
Callou collei we'll code the way
Of prime numbers and pings!
a common use for bitwise operations is to use them with flags:of course, in C++, you can use enums instead of the defines.Code:#define MYPROG_OPT1 0x1 #define MYPROG_OPT2 0x2 #define MYPROG_OPT3 0x4 ... int flags=0; flags |= MYPROG_OPT1; //set opt 1 ... if (flags & MYPROG_OPT1) { //opt_1 is set } else if (flags & MYPROG_OPT2) { //opt_2 is set } if ((flags & MYPROG_OPT1) && (flags & MYPROG_OPT3)) { //sweet combo move } flags=0; //clear flags
Last edited by robwhit; 08-08-2007 at 11:13 AM. Reason: thanks matsp
Good point, but there are plenty of cases where bit-manipulation is done in drivers and hardware controlling software. It may be out of ignorance, or it may be because the regiser has multiple definitions (yes, you can create unions of bit fields, but it can get pretty messy doing it that way too).Originally Posted by QuestionC
--
Mats
You mean:Code:flags |= MYPROG_OPT1; //set opt 1Many people still use #define for defining constants, but certainly enums do exist in plain C too, I think first time I heard about them was 15 years ago, or so...of course, in C++, you can use enums instead of the defines.
--
Mats
Bitfields are awful, IMHO. They were invented as a memory optimization, not a clarity thing. I spent a few minutes poking around the Linux kernel driver collection and I don't see any bitfields, nor would I expect any. They are confusing, compiler support is flaky, missing, or nonstandard (a big reason why the Linux kernel doesn't use them), they don't really help anything, etc.
Come now, surely you jest. Unioning together a few bitfields always provides that extra bit of clarity needed in a program.I've only used bitfields (and unions of bitfields, for that matter) in needlessly complex contest code.
If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein
Are we talking about this bit field?
I thought I just used bit fields in a Sudoku program (first nine bits represent candidates for each particular cell) and I think this was quite useful as it would cut out some inner loops (checking for coinciding candidates etc). The code is mostly quite unreadable anyway, but I think it would be more so, if I used an array for candidates instead of a single unsigned.
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
In graphics bit shifting is used to convert a set of red, green and blue colour elements to an RGB colour value. Its also used in combination with bitwise anding for extracting the colour elements too.
Obviously, when trying to support multiple architectures, it gets more tricky, even if the same "manufacturer" compiler is being used. It gets worse supporting multiple compilers.
On the other hand, I've worked with a graphics driver for Windows which used quite a lot of register definitions written as structs with bitfields. Since there were MANY bitfields in almost every register, it was much better to use bitfields than shifts and masks to manipulate the data in those registers.
I'm not religous about either solution - both works if they are correctly used (and tested with the compiler).
In my opinion, a lot of things in Linux are the way they are because Linus thinks they should be that way - not that I could argue that he's wrong very often, but I think this is more to do with things than the direct technical aspects - a lot of things in software engineering is about making choices and deciding on a structure/pattern to follow - it is much better to have a dozen drivers written with similar methods than to have each driver written with a "personal style", because once you've figured out things for the one driver, the next one is much easier to follow.
--
Mats
