Setting the nth bit of a 64 bit buffer to a given value (1 or 0)?

Discussion in 'Programmer's Corner' started by spinnaker, Apr 24, 2011.

  1. spinnaker

    Thread Starter AAC Fanatic!

    Oct 29, 2009
    4,887
    1,017
    Seems I am having brain freeze. I can't figure out how to do this one.

    Say I have an array of 8 unsigned chars

    unsigned char buffer[8];

    Which would make 64 bits in total.

    Using C, how do I set the nth bit of the buffer to a given value (1 or 0)?

    I'm guessing I would need to do an exclusive or but I am having a hard time figuring an efficient way to determine both bit and bit position.
     
  2. hgmjr

    Moderator

    Jan 28, 2005
    9,030
    214
    This is place where I would use the modulo operator "%". Modulo 8 would give you the byte and remainder would give you the bit position within the byte.

    hgmjr
     
  3. THE_RB

    AAC Fanatic!

    Feb 11, 2008
    5,435
    1,305
    To set bit 17 (for instance);

    Code ( (Unknown Language)):
    1.  
    2. // code to set a bit 0-63 in a 64 bit buffer, bit 0 is at the left
    3. n = 17;    // is the bit to set
    4. b = 0;     // will be the byte that contains that bit
    5. while(n >= 8)
    6. {
    7.   n -= 8;  // sub 8 bits
    8.   b++;     // go to next byte
    9. }
    10. // when it gets here b is the correct byte, and n is the bit within that byte
    11. mask = 0b10000000;    // a bit to shift
    12. while(n > 0)
    13. {
    14.   mask = (mask >> 1);   // shift that bit right
    15.   n--;
    16. }
    17. buffer[b] |= mask;    // set that bit
    18. [/b]


    This uses successive subtraction instead of modulus, which has a small advantage that it does not require division.
     
  4. t06afre

    AAC Fanatic!

    May 11, 2009
    5,939
    1,222
    The basics of bit twiddling is about using bitwise and,or,and xor. And of course shift operations. You can google bit twiddling. Take a look at the 4 or 5 first hits. You will find some macros that handle 1 bit at the time. But if you want to set several bits at the same time use techniques that change all the the bits using bitwise and,or,and xor
     
  5. John P

    AAC Fanatic!

    Oct 14, 2008
    1,634
    224
    If "value" is 0 or nonzero, causing the bit to be cleared or set, then I think this does it:

    Code ( (Unknown Language)):
    1.  
    2.   if (value)
    3.     buffer[n >> 3] |= (1 << (n & 7));
    4.   else
    5.     buffer[n >> 3] &= ~(1 << (n & 7));
    6.  
     
  6. Markd77

    Senior Member

    Sep 7, 2009
    2,803
    594
    I'd be interested to see what the compiler comes out with. I think I could do it in around 30 cycles in PIC16 assembler using the FSR for the byte and a table to convert the bitnumber to a mask before XORing.
     
  7. hgmjr

    Moderator

    Jan 28, 2005
    9,030
    214
    Similar to John P's approach, I have used the modulo operator '%' and I have also added a mask to the test of bit-value. The mask is not a critical measure to take. It just makes it clearer to someone trying to interpret the code for the first time.

    Code ( (Unknown Language)):
    1. void bit_modify(unsigned char bit_value, unsigned char bit_number)
    2. {
    3.    if (bit_value & 0x01)  // LSB to determine what action to take...
    4.    {
    5.       buffer[bit_number>>3] |= (1<<(bit_number%8));
    6.    }
    7.    else
    8.    {
    9.       buffer[bit_number>>3] &= ~(1<<(bit_number%8));
    10.    }
    11. }
    12.  
    hgmjr
     
  8. someonesdad

    Senior Member

    Jul 7, 2009
    1,585
    141
    You don't give the compiler and platform, so the answer will certainly depend on that. If I was doing this on a PC with a compiler that let me use 64 bit integers, I'd try casting the array's pointer to a 64 bit integer and then use an AND/OR/XOR (depending on your needs) with a 1 << n. Of course, this would never work on a little embedded platform. And it's not portable code (endianness and integer sizes), so I'd ding anyone who used it in a code review unless it was absolutely necessary.

    A contiguous array in memory is often used for a big bit field similar to what you're doing. I've made bitfields up to 10^9 bits using strings on the heap. You need to figure out the bit's address with an integer division and a mod -- it's pretty straightforward and can be made to work for any size that's within the range of the platform's integer.

    Here's a snippet of C++ code that compiles and runs on my PC with g++ (MinGW 3.4.5) that shows the basic idea mentioned in the first paragraph:
    Code ( (Unknown Language)):
    1.  
    2. #include <iostream>
    3. #include <stdint.h>
    4. int main(void)
    5. {
    6.     int64_t i, x = 1;
    7.     for (i=0; i<64; i++)
    8.         std::cout << (x << i) << std::endl;
    9. }
    10.  
    11.  
    Note those parentheses are kinda important. :p And I know it's not C like you asked about...
     
  9. John P

    AAC Fanatic!

    Oct 14, 2008
    1,634
    224
    This was interesting enough that I wrote a little program to do it.

    Code ( (Unknown Language)):
    1.  
    2. 0000                00353 .................... const int lookup[8] = {1, 2, 4, 8, 16, 32, 64, 128};
    3. 0004 100A           00354 BCF    0A,0
    4. 0005 108A           00355 BCF    0A,1
    5. 0006 110A           00356 BCF    0A,2
    6. 0007 0782           00357 ADDWF  02,F
    7. 0008 3401           00358 RETLW  01
    8. 0009 3402           00359 RETLW  02
    9. 000A 3404           00360 RETLW  04
    10. 000B 3408           00361 RETLW  08
    11. 000C 3410           00362 RETLW  10
    12. 000D 3420           00363 RETLW  20
    13. 000E 3440           00364 RETLW  40
    14. 000F 3480           00365 RETLW  80
    15. 0000                00366 ....................  
    16. 0000                00367 .................... #inline
    17. 0000                00368 .................... void setabit(int value, int n)
    18. 0000                00369 .................... {
    19. 0000                00370 ....................  fsr = n;                                                    // Equivalant to fsr = buffer + (n >> 3)
    20. 0035 0829           00371 MOVF   29,W
    21. 0036 0084           00372 MOVWF  04
    22. 0000                00373 ....................  fsr >>= 3;
    23. 0037 0C84           00374 RRF    04,F
    24. 0038 0C84           00375 RRF    04,F
    25. 0039 0C84           00376 RRF    04,F
    26. 003A 301F           00377 MOVLW  1F
    27. 003B 0584           00378 ANDWF  04,F
    28. 0000                00379 ....................  fsr += buffer;
    29. 003C 3020           00380 MOVLW  20
    30. 003D 0784           00381 ADDWF  04,F
    31. 0000                00382 ....................  
    32. 0000                00383 ....................  if (value)
    33. 003E 08A8           00384 MOVF   28,F
    34. 003F 1903           00385 BTFSC  03,2
    35. 0040 2848           00386 GOTO   048
    36. 0000                00387 ....................      indirect |= lookup[n & 7];
    37. 0041 0829           00388 MOVF   29,W
    38. 0042 3907           00389 ANDLW  07
    39. 0043 2004           00390 CALL   004
    40. 0044 00F8           00391 MOVWF  78
    41. 0045 0878           00392 MOVF   78,W
    42. 0046 0480           00393 IORWF  00,F
    43. 0000                00394 ....................  else
    44. 0047 284F           00395 GOTO   04F
    45. 0000                00396 ....................      indirect &= ~lookup[n & 7];
    46. 0048 0829           00397 MOVF   29,W
    47. 0049 3907           00398 ANDLW  07
    48. 004A 2004           00399 CALL   004
    49. 004B 00F8           00400 MOVWF  78
    50. 004C 0878           00401 MOVF   78,W
    51. 004D 3AFF           00402 XORLW  FF
    52. 004E 0580           00403 ANDWF  00,F
    53. 0000                00404 .................... }
    54.  
    This is written for the compiler I use, an ancient version of the CCS compiler. Newer editions may well be more efficient. As it was, I was so offended by the way the compiler dealt with the line
    fsr = buffer + (n >> 3)
    that I rewrote it as 3 separate lines. The compiler wanted to use scratchpad registers, which isn't necessary at all. But then notice how the compiler has added
    MOVWF 78
    MOVF 78,W
    after the call-return process! It won't accept that it has the right value in the W register; it has to come from some other location, even if it has to be put there specially! That's so ridiculous that I'd be tempted to put in a few lines of assembly to improve it.

    I assume it's clear how the use of "fsr" and "indirect" works. I do that all the time to nudge the compiler into more efficient code.

    Edited later to say: I lost track of the fact that this query was a general one, not limited to the PIC processor. If it's real-computer stuff, then I'd stick with my first suggestion. It's not worth fooling around with details unless you really have a big program to deal with.
     
    Last edited: Apr 26, 2011
Loading...