Bit shifting/manipulation.

This is a discussion on Bit shifting/manipulation. within the C++ Programming forums, part of the General Programming Boards category; I have been reading up on some of this material and I keep finding myself asking the same question over ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    9

    Bit shifting/manipulation.

    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

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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!

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    some data streams like networking are defined on the bit level, so you'd need to be able to access that.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    9
    Thanks guys for getting back to me so quickly, I think I understand them now.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    There are many different uses for bitshifts. The most common is divide/multiply by powers of 2
    Code:
       x >> 1;    // x / 2
       x >> 2;    // x / 4
       x >> 3;    // x / 8
       ...
       x >> 15;  // x / 32768
    The same obviously applies for multiplication.

    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

  6. #6
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398
    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.

  7. #7
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    "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!

  8. #8
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    a common use for bitwise operations is to use them with flags:
    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
    of course, in C++, you can use enums instead of the defines.
    Last edited by robwhit; 08-08-2007 at 11:13 AM. Reason: thanks matsp

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by QuestionC View Post
    "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.
    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).

    --
    Mats

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by robwhit View Post
    a common use for bitwise operations is to use them with flags:
    Code:
    #define MYPROG_OPT1 0x1
    #define MYPROG_OPT2 0x2
    #define MYPROG_OPT3 0x4
    
    ...
    
    int flags=0;
    flags &= MYPROG_OPT1; //set opt 1
    You mean:
    Code:
    flags |= MYPROG_OPT1; //set opt 1
    of course, in C++, you can use enums instead of the defines.
    Many 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...

    --
    Mats

  11. #11
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,160
    Quote Originally Posted by matsp View Post
    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).
    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.

  12. #12
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    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

  13. #13
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  14. #14
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by brewbuck View Post
    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.
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bit manipulation
    By Neo1 in forum C++ Programming
    Replies: 8
    Last Post: 03-24-2008, 11:53 AM
  2. porting application from 32 bit to 64 bit error
    By gandalf_bar in forum Linux Programming
    Replies: 1
    Last Post: 09-14-2005, 09:20 AM
  3. Bit processing in C
    By eliomancini in forum C Programming
    Replies: 8
    Last Post: 06-07-2005, 10:54 AM
  4. Bitwise Operators - Setting and Retreiving a Bit
    By Spono in forum C Programming
    Replies: 2
    Last Post: 11-04-2003, 01:09 PM
  5. Bit Manipulation Questions
    By CPPNewbie in forum C++ Programming
    Replies: 7
    Last Post: 08-12-2003, 02:17 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21