Thread: Bitshift on 64-bit integers.

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    54

    Bitshift on 64-bit integers.

    Hi, I have two questions. How do you access 8-byte ingeters in C, and secondly, how do you perform bitshifting on integers of those size? I'm using LCC compiler, Windows 2000.

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Use 'long long' as the type to get a 64-bit int. You do bitshifting the same way as you would with any other int.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User
    Join Date
    Feb 2005
    Posts
    54
    I was able to get that part, but when i tried to shift past 32 bits, it wouldnt let me. Is there a way to get by that? I'm basically trying to implement the DES encryption algorithm.

    I'm trying to manipulate a series of bits in chunks.
    Last edited by maththeorylvr; 03-08-2005 at 01:43 PM.

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    You can do the shifting in 2 statements:
    Code:
    itsme@dreams:~/C$ cat longlong.c
    #include <stdio.h>
    
    int main(void)
    {
      long long x = 1;
    
      // Left shift 40 times
      x <<= 20;
      x <<= 20;
    
      printf("x is %lld\n", x);
      return 0;
    }
    Code:
    itsme@dreams:~/C$ ./longlong
    x is 1099511627776
    If you understand what you're doing, you're not learning anything.

  5. #5
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Code:
    #include <stdio.h>
    #include <stdint.h>
    #include <inttypes.h>
    
    int main( void )
    {
       int shift;
       for ( shift = 0; shift < 64; ++shift )
       {
          uint64_t a = 1ULL << shift, b = 1 << shift;
          printf("shift = %2d, a = %016"PRIx64", b = %016"PRIx64"\n", shift, a, b);
       }
       return 0;
    }
    
    /* my output (trimmed)
    shift =  0, a = 0000000000000001, b = 0000000000000001
    shift =  1, a = 0000000000000002, b = 0000000000000002
    ...
    shift = 30, a = 0000000040000000, b = 0000000040000000
    shift = 31, a = 0000000080000000, b = 0000000080000000
    shift = 32, a = 0000000100000000, b = 0000000000000001
    shift = 33, a = 0000000200000000, b = 0000000000000002
    ...
    shift = 62, a = 4000000000000000, b = 0000000040000000
    shift = 63, a = 8000000000000000, b = 0000000080000000
    */
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  6. #6
    Registered User
    Join Date
    Feb 2005
    Posts
    54
    Quote Originally Posted by Dave_Sinkula
    Code:
    #include <stdio.h>
    #include <stdint.h>
    #include <inttypes.h>
    
    int main( void )
    {
       int shift;
       for ( shift = 0; shift < 64; ++shift )
       {
          uint64_t a = 1ULL << shift, b = 1 << shift;
          printf("shift = %2d, a = %016"PRIx64", b = %016"PRIx64"\n", shift, a, b);
       }
       return 0;
    }
    
    /* my output (trimmed)
    shift =  0, a = 0000000000000001, b = 0000000000000001
    shift =  1, a = 0000000000000002, b = 0000000000000002
    ...
    shift = 30, a = 0000000040000000, b = 0000000040000000
    shift = 31, a = 0000000080000000, b = 0000000080000000
    shift = 32, a = 0000000100000000, b = 0000000000000001
    shift = 33, a = 0000000200000000, b = 0000000000000002
    ...
    shift = 62, a = 4000000000000000, b = 0000000040000000
    shift = 63, a = 8000000000000000, b = 0000000080000000
    */

    It works now.
    Last edited by maththeorylvr; 03-08-2005 at 04:14 PM.

  7. #7
    Registered User
    Join Date
    Feb 2005
    Posts
    30
    hi maththeorylvr

    I'm just learning about bit shifting...
    since you're talking about bit shifting, can you explain bit shifting in this example:

    int id = 256;
    char buffer[4];

    buffer[0] = (char)(id >>24);

    hexadecimal representation of 256 is 0000 0100
    I just don't understand what " >>" does..the last 8 bits are all shifted to the left? in this assignment statement the first 8 bits are taken in consideration only?
    after being shifted 0000 0100 becomes 00 0000 01 ??

    thanks for your help

  8. #8
    Registered User
    Join Date
    Feb 2005
    Posts
    54
    I think >> x shifts all bits x positions to the right, and fills any extra spaces with 0. Its the same as dividing by 2^(x)

  9. #9
    Registered User
    Join Date
    Feb 2005
    Posts
    54
    Bitshift operations not working when I go past 32, again. Here is the code I'm using to break the bitshifting up into parts when the number I want to shift by exceeds 32. Its not working.

    Code:
    uint64_t shift(uint64_t to_shift, int pos) {
      uint64_t temp; 
      
             while (pos > 0) {
             if (pos == 0) break;
             if (pos > 31) {
             to_shift = to_shift << 31;
             temp = to_shift;
             pos = pos - 31;
             } else {
           //  printf("Shifted: b = %016"PRIx64"\n", to_shift);
             to_shift = temp << pos;
              printf("Position2: %lld\n", to_shift);
             break;
             }       
             }
          //   printf("Shifted: b = %016"PRIx64"\n", to_shift);
             return to_shift;
    }
    I can do something like:
    Code:
     x = x << 20;
                                         x = x << 20;
    , but when trying the same thing with a variable, it fails. Since I only have to use special shifts when it exceeds 32 but is less than 56, I can just hardcode it to work like that if nothing else works, for each 23 between 32 and 56. Any suggestions welcomed.
    Last edited by maththeorylvr; 03-08-2005 at 05:52 PM.

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    184
    hello guys,

    i am new to this bit shifting operation and stuff

    can any one tell me what this bit of code is and how is works

    originally posted by Dave_Sinkula
    Code:
    uint64_t a = 1ULL << shift, b = 1 << shift;
          printf("shift = %2d, a = %016"PRIx64", b = %016"PRIx64"\n", shift, a, b);
    thax very much

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You could always read the faq entry. All it does is shift an unsigned long long 1 to the left shift places, storing that in a. It then does that for another one, but this one isn't forced to be an unsigned long long. That value goes into b. Then it prints some output.

    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    AFAIK bit shifting on uint64 may not do what you want unless the compiler is ready to handle it. You could use the integral MMX registers to accomplish this which might be what MSVC already does or perhaps it concatenates two 32-bit registers. Either way if your value is being stored in a 32-bit register it is possible that your data is being shifted out of the operation. Check some of the CPU flags to see if this is happening. All a bit shift is, is a simple division or multiplication.

    In base 10 if we move the decimal to the right what happens? We essentially divide by 10. If we move the decimal point to the left, what happens? We multiply by 10. The number you shift by is simply the base raised to that power. So if you right shift by 1 in base 10 you are really dividing by the base (10) raised to 1. 10 raised to the 1st is 10, so you are dividing by 10.


    100 >> 1 = 100 / (10^1) = 100/10 = 10
    100 << 1 =100 * (10^1) = 100*10=1000

    Now for base 2 the only difference is that instead of it being 10 raised to the power, it is 2 raised to the power.

    In base 2:

    2 >> 1 = 2 / 2(2^1) = 2/2 = 1
    2 << 1 =2 * (2^1) = 2*2 = 4

    In binary you can see what is happening. This is called a bit shift because you are shifting the bits. But when you shift the bits you get the multiplication and/or division operation.

    2 = 10 in binary

    Shift right by 1:
    01 or 1 in binary

    Now shift left:
    ................1 = 1....(2^0)...(x*1)
    ..............10 = 2....(2^1)...(x*2)
    ............100 = 4....(2^2)...(x*4)
    ..........1000 = 8....(2^3)...(x*8)
    ........10000 = 16..(2^4)...(x*16)
    ......100000 = 32..(2^5)...(x*32)
    ....1000000 = 64..(2^6)...(x*64)
    ..10000000 = 128 (2^7)...(x*128)
    100000000 = 256 (2^8)...(x*256)

    We just shifted left and you can see what happened. So the result of a shift left is multiplying by the quantity 2 raised to the shift value. Now don't get confused by my base 10 example earlier, I was just trying to explain it with a commonly used base.

    Now suppose you shift by a value that is larger than what can be contained in your data type. For instance let's say you are using an 8-bit data type and shift left by 9. There are not enough bits to shift left by 9 so the value is being shifted out of the equation. This will set a CPU overflow flag (OF=1) and may or may not place the value in another register - depending on the actual CPU opcode that was executed.

  13. #13
    Registered User
    Join Date
    Feb 2005
    Posts
    54
    Here is a problem I'm trying to resolve. Its mainly a code length problem. I want to get around having to hard code every single bit shift, but uint_64 doesnt shift correctly when I try to use a variable to represent the number of bits to shift:


    This was my first choice:

    You can assum pos will not exceed 63.
    Code:
    uint64_t shift(uint64_t to_shift, int pos) {
    if (pos < 32) to_shift = to_shift << pos;
    else {
    to_shift = to_shift << 32;
    to_shift = to_shift << (pos - 32);
    }
    }

    Code:
    uint64_t shift(uint64_t to_shift, int pos) {
       if (pos == 1){ to_shift = to_shift << 1; }
        else if (pos == 2){ to_shift = to_shift << 2; }
        else if (pos == 3){ to_shift = to_shift << 3; }
        else if (pos == 4){ to_shift = to_shift << 4; }
        else if (pos == 5){ to_shift = to_shift << 5; }
        else if (pos == 6){ to_shift = to_shift << 6; }
        else if (pos == 7){ to_shift = to_shift << 7; }
        else if (pos == 8){ to_shift = to_shift << 8; }
        else if (pos == 9){ to_shift = to_shift << 9; }
        else if (pos == 10){ to_shift = to_shift << 10; }
        else if (pos == 11){ to_shift = to_shift << 11; }
        else if (pos == 12){ to_shift = to_shift << 12; }
        else if (pos == 13){ to_shift = to_shift << 13; }
        else if (pos == 14){ to_shift = to_shift << 14; }
        else if (pos == 15){ to_shift = to_shift << 15; }
        else if (pos == 16){ to_shift = to_shift << 16; }
        else if (pos == 17){ to_shift = to_shift << 17; }
        else if (pos == 18){ to_shift = to_shift << 18; }
        else if (pos == 19){ to_shift = to_shift << 19; }
        else if (pos == 20){ to_shift = to_shift << 20;  }
        else if (pos == 21){ to_shift = to_shift << 21;  }
        else if (pos == 22){ to_shift = to_shift << 22;  }
        else if (pos == 23){ to_shift = to_shift << 23;  }
        else if (pos == 24){ to_shift = to_shift << 24;  }
        else if (pos == 25){ to_shift = to_shift << 25;  }
        else if (pos == 26){ to_shift = to_shift << 26; }
        else if (pos == 27){ to_shift = to_shift << 27; }
        else if (pos == 28){ to_shift = to_shift << 28; }
        else if (pos == 29){ to_shift = to_shift << 29;}
        else if (pos == 30){ to_shift = to_shift << 30; }
        else if (pos == 31){ to_shift = to_shift << 1; to_shift = to_shift << 30; }
        else if (pos == 32){ to_shift = to_shift << 1; to_shift = to_shift << 31; }
        else if (pos == 33){ to_shift = to_shift << 1; to_shift = to_shift << 32; }
        else if (pos == 34){ to_shift = to_shift << 2; to_shift = to_shift << 32; }
        else if (pos == 35){ to_shift = to_shift << 3; to_shift = to_shift << 32; }
        else if (pos == 36){ to_shift = to_shift << 4; to_shift = to_shift << 32; }
        else if (pos == 37){ to_shift = to_shift << 5; to_shift = to_shift << 32; }
        else if (pos == 38){ to_shift = to_shift << 6; to_shift = to_shift << 32; }
        else if (pos == 39){ to_shift = to_shift << 7; to_shift = to_shift << 32; }
        else if (pos == 40){ to_shift = to_shift << 8; to_shift = to_shift << 32; }
        else if (pos == 41){ to_shift = to_shift << 9; to_shift = to_shift << 32; }
        else if (pos == 42){ to_shift = to_shift << 10; to_shift = to_shift << 32; }
        else if (pos == 43){ to_shift = to_shift << 11; to_shift = to_shift << 32; }
        else if (pos == 44){ to_shift = to_shift << 12; to_shift = to_shift << 32; }
        else if (pos == 45){ to_shift = to_shift << 13; to_shift = to_shift << 32; }
        else if (pos == 46){ to_shift = to_shift << 14; to_shift = to_shift << 32; }
        else if (pos == 47){ to_shift = to_shift << 15; to_shift = to_shift << 32; }
        else if (pos == 48){ to_shift = to_shift << 16; to_shift = to_shift << 32; }
        else if (pos == 49){ to_shift = to_shift << 17; to_shift = to_shift << 32; }
        else if (pos == 50){ to_shift = to_shift << 18; to_shift = to_shift << 32; }
        else if (pos == 51){ to_shift = to_shift << 19; to_shift = to_shift << 32; }
        else if (pos == 52){ to_shift = to_shift << 20; to_shift = to_shift << 32; }
        else if (pos == 53){ to_shift = to_shift << 21; to_shift = to_shift << 32; }
        else if (pos == 54){ to_shift = to_shift << 22; to_shift = to_shift << 32; }
        else if (pos == 55){ to_shift = to_shift << 23; to_shift = to_shift << 32; }
        else if (pos == 56){ to_shift = to_shift << 24; to_shift = to_shift << 32; }
        else if (pos == 57){ to_shift = to_shift << 25; to_shift = to_shift << 32; }
        else if (pos == 58){ to_shift = to_shift << 26; to_shift = to_shift << 32; }
        else if (pos == 59){ to_shift = to_shift << 27; to_shift = to_shift << 32; }
        else if (pos == 60){ to_shift = to_shift << 28; to_shift = to_shift << 32; }
        else if (pos == 61){ to_shift = to_shift << 29; to_shift = to_shift << 32; }
        else if (pos == 62){ to_shift = to_shift << 30; to_shift = to_shift << 32; }
        else if (pos == 63){ to_shift = to_shift << 31; to_shift = to_shift << 32; }
        else if (pos == 64){ to_shift = to_shift << 32; to_shift = to_shift << 32; } 
        return to_shift; 
    }
    Any suggestions?

  14. #14
    Registered User
    Join Date
    Feb 2005
    Posts
    54
    I'm using the lcc-32 compiler.

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    uint64_t shift(uint64_t to_shift, int pos) {
        if( pos > 32 )
        {
            to_shift <<= 32;
            pos -= 32;
        }
        return to_shift << pos;
    }
    Something like that perhaps?

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  2. A few questions about 64 bit and Windows...
    By yaya in forum Tech Board
    Replies: 9
    Last Post: 08-28-2008, 08:49 AM
  3. 32 bit or 64 bit allignment ?! gcc options??
    By mynickmynick in forum C Programming
    Replies: 3
    Last Post: 07-29-2008, 02:43 AM
  4. 64 bit testing
    By DrSnuggles in forum C++ Programming
    Replies: 7
    Last Post: 11-20-2007, 03:20 AM
  5. Writing 64 bit value in hex to a string
    By rahulgbe in forum C Programming
    Replies: 2
    Last Post: 03-18-2006, 01:15 PM