![](templates/subSilver/images/CCSLogo.jpg) |
![CCS C Software and Maintenance Offers](templates/subSilver/images/forumAd6.jpg) |
View previous topic :: View next topic |
Author |
Message |
Neutone
Joined: 08 Sep 2003 Posts: 839 Location: Houston
|
What is a simple way to verify only one bit in a byte is set |
Posted: Fri Feb 13, 2004 4:48 pm |
|
|
I though about testing each bit and incrementing a counter but that does not seem very smooth. |
|
![](templates/subSilver/images/spacer.gif) |
Guest
|
|
Posted: Fri Feb 13, 2004 5:40 pm |
|
|
If no bits are set then the value is zero right? So can't you just check to see if the value != 0 |
|
![](templates/subSilver/images/spacer.gif) |
Hans Wedemeyer
Joined: 15 Sep 2003 Posts: 226
|
Please clarify |
Posted: Fri Feb 13, 2004 6:39 pm |
|
|
Do you need to know if a particular bit is set ?
or just any bit ?
or a table of any bits ? |
|
![](templates/subSilver/images/spacer.gif) |
rwyoung
Joined: 12 Nov 2003 Posts: 563 Location: Lawrence, KS USA
|
|
Posted: Fri Feb 13, 2004 6:59 pm |
|
|
Test for exact power of 2
I have the algorithm at home some place. I'll try and remember to look it up when I go home tonight. _________________ Rob Young
The Screw-Up Fairy may just visit you but he has crashed on my couch for the last month! |
|
![](templates/subSilver/images/spacer.gif) |
dazza Guest
|
? |
Posted: Sat Feb 14, 2004 4:03 am |
|
|
what about...
Code: |
for(i=0;i<8;i++) {
if(bit_test(YourVariable,i) {
BitArray(i)=1;
}
else {
BitArray(i)=0;
}
}
|
maybe some syntax needs correcting but you get the idea!? |
|
![](templates/subSilver/images/spacer.gif) |
rwyoung
Joined: 12 Nov 2003 Posts: 563 Location: Lawrence, KS USA
|
|
Posted: Sat Feb 14, 2004 1:10 pm |
|
|
I found my book. I thought it had an example of a sneaky way to test for an exact power of two. It doesnt. What it does have is a nifty way of counting how many ones are in a binary value. If you did that and it came back as 1 then you know it was a power of 2.
The down side to this algorithm is it is set up for 32-bit integers but here it is anyway:
Code: |
int pop(unsigned x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0f0f0f0f;
x = x + (x >> 8);
x = x + (x >> 16);
return (x & 0x0000003f);
}
|
this is supposed to be a simplified and faster version of
Code: |
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
|
All this came from Warren's "Hacker's Delight". I have used the bit counting trick on a PC but I haven't tried to port it over to a PIC and work with 8 or 16 bit integers but it should be possible. The best thing is no loops.
There are also some slick ways of rounding up or down to the next power of 2 and I have the feeling that those methods could be used for detecting an exact power of 2 _________________ Rob Young
The Screw-Up Fairy may just visit you but he has crashed on my couch for the last month! |
|
![](templates/subSilver/images/spacer.gif) |
dyeatman
Joined: 06 Sep 2003 Posts: 1924 Location: Norman, OK
|
Bit Test |
Posted: Sat Feb 14, 2004 6:36 pm |
|
|
FWIW, my method is (pseudocode):
1. set a temp var (byte, word, dword as req'd) to 1
2. set up a loop for the total # of bits to check
3. XOR the temp var with the byte/word/dword under test looking for zero
4. do a left shift of the temp var
5. save result as required here
5. loop to step 3
An option of a FOR loop or a WHILE loop testing for a max val on the temp variable.
This is very efficient since it tests for zero and is super fast. It has worked well for me on a number of occasions.
dave |
|
![](templates/subSilver/images/spacer.gif) |
KerryW Guest
|
|
Posted: Sun Feb 15, 2004 8:49 am |
|
|
Here's what I would do:
if(test_byte==0) printf("0 bits set\n");
while(!(test_byte&0x80)) test_byte<<=1; // shift until MSB is set
if(test_bye==0x80) printf("1 bit set\n"); // if MSB is ONLY bit set
else printf("Multiple bits set\n");
If you need to know WHICH bit is set, count the # of shifts and subtract from 7. |
|
![](templates/subSilver/images/spacer.gif) |
Humberto
Joined: 08 Sep 2003 Posts: 1215 Location: Buenos Aires, La Reina del Plata
|
|
Posted: Sun Feb 15, 2004 9:26 am |
|
|
Hi Neutone,
Iīm aware of your knowledge, capacity and experience and itīs strange for me your question, itīs a widespread question and I understand it in different ways and situations:
1) If you know wich bit you expect to change, just make an AND to isolate such bit.
2) If you doesnīt know wich bit has changed, test one extreme bit shifting one position in a loop.
3) If you know that only one bit is going to change, you will clear the variable prior to call such function and then test: var != 0
They looks like silly answers..
yes they are!!!
regards,
Humberto |
|
![](templates/subSilver/images/spacer.gif) |
Neutone
Joined: 08 Sep 2003 Posts: 839 Location: Houston
|
|
Posted: Sun Feb 15, 2004 8:08 pm |
|
|
I have to handel an incomming packet that has several command bits all located within a byte. If more than one bit is set that indicates an error or an incorrectly formatted packet. In the case of an incorrectly formatted packet I have to reject the packet. My original thought was to to do this;
Code: |
Count_Of_Command_Bits=0;
Packet_Error=0;
if(bit_test(data, 0)) ++Count_Of_Command_Bits;
if(bit_test(data, 1)) ++Count_Of_Command_Bits;
if(bit_test(data, 2)) ++Count_Of_Command_Bits;
if(bit_test(data, 3)) ++Count_Of_Command_Bits;
if(bit_test(data, 4)) ++Count_Of_Command_Bits;
if(bit_test(data, 5)) ++Count_Of_Command_Bits;
if(bit_test(data, 6)) ++Count_Of_Command_Bits;
if(bit_test(data, 7)) ++Count_Of_Command_Bits;
if(Count_Of_Command_Bits>1) Packet_Error=1;
|
It just seems like this is going the long way to do something simple and it doesn't read very well. |
|
![](templates/subSilver/images/spacer.gif) |
Al
Joined: 13 Nov 2003 Posts: 28 Location: Belfast
|
|
Posted: Mon Feb 16, 2004 6:50 am |
|
|
Hi Neutone,
I haven't tested this code but it is just an idea. In theory it should work.
if(packet!=0){
for(i=7;!bit_test(packet, i);i--) ;
// i has found first errored bit
if(i>0) {
// now start new search at position i (i.e. at last errored bit)
for(j=i;!bit_test(packet, j);j--) ;
}
if(j>0) printf("Too many errors");
}
Having posted this - I realised you may need to check what happens if the very last bit (i.e. when j=0) is set as well as one other _________________ Alan Murray |
|
![](templates/subSilver/images/spacer.gif) |
neil
Joined: 08 Sep 2003 Posts: 128
|
look for a binary value |
Posted: Tue Feb 17, 2004 5:34 am |
|
|
Why not try looking for a binary multiple, 1,2,4,8, etc. You could create a mask, which is placed in a loop, on each pass of the loop, bit shift the mask one place, AND it with the data byte and test STATUS,Z (in asm?) for a zero condition, also check STATUS,C for a carry condition. If zero, and no carry, the byte was a binary value, eg. only one bit set.
Am I *thinking* here? I think I may have just suggested a variation on the other ways people have already suggested! Maybe that's the right way? ![Rolling Eyes](images/smiles/icon_rolleyes.gif) |
|
![](templates/subSilver/images/spacer.gif) |
Neutone
Joined: 08 Sep 2003 Posts: 839 Location: Houston
|
Re: look for a binary value |
Posted: Tue Feb 17, 2004 9:11 am |
|
|
neil wrote: | Why not try looking for a binary multiple, 1,2,4,8, etc. You could create a mask, which is placed in a loop, on each pass of the loop, bit shift the mask one place, AND it with the data byte and test STATUS,Z (in asm?) for a zero condition, also check STATUS,C for a carry condition. If zero, and no carry, the byte was a binary value, eg. only one bit set.
Am I *thinking* here? I think I may have just suggested a variation on the other ways people have already suggested! Maybe that's the right way? ![Rolling Eyes](images/smiles/icon_rolleyes.gif) |
All other things being equal.
Code: |
data=Comm1_Buffer[5];
Count_Of_Command_Bits=0;
if(bit_test(data, 0)) ++Count_Of_Command_Bits;
if(bit_test(data, 1)) ++Count_Of_Command_Bits;
if(bit_test(data, 2)) ++Count_Of_Command_Bits;
if(bit_test(data, 3)) ++Count_Of_Command_Bits;
if(bit_test(data, 4)) ++Count_Of_Command_Bits;
if(bit_test(data, 5)) ++Count_Of_Command_Bits;
if(bit_test(data, 6)) ++Count_Of_Command_Bits;
if(bit_test(data, 7)) ++Count_Of_Command_Bits;
Bit_Mask=1;
for(i=8;i>0;i--)
{ if(Bit_Mask&data)++Count_Of_Command_Bits;
Bit_Mask<<1;
}
if(Count_Of_Command_Bits>1)
{ Bad_Data_Value=1;
Comm1_Buffer[5]=0;
}
|
Compiles like this
Code: |
.................... Count_Of_Command_Bits=0;
3944: CLRF xFD
....................
.................... if(bit_test(data, 0)) ++Count_Of_Command_Bits;
3946: BTFSC xFE.0
3948: INCF xFD,F
.................... if(bit_test(data, 1)) ++Count_Of_Command_Bits;
394A: BTFSC xFE.1
394C: INCF xFD,F
.................... if(bit_test(data, 2)) ++Count_Of_Command_Bits;
394E: BTFSC xFE.2
3950: INCF xFD,F
.................... if(bit_test(data, 3)) ++Count_Of_Command_Bits;
3952: BTFSC xFE.3
3954: INCF xFD,F
.................... if(bit_test(data, 4)) ++Count_Of_Command_Bits;
3956: BTFSC xFE.4
3958: INCF xFD,F
.................... if(bit_test(data, 5)) ++Count_Of_Command_Bits;
395A: BTFSC xFE.5
395C: INCF xFD,F
.................... if(bit_test(data, 6)) ++Count_Of_Command_Bits;
395E: BTFSC xFE.6
3960: INCF xFD,F
.................... if(bit_test(data, 7)) ++Count_Of_Command_Bits;
3962: BTFSC xFE.7
3964: INCF xFD,F
....................
.................... Bit_Mask=1;
3966: MOVLW 01
3968: MOVLB 2
396A: MOVWF x00
.................... for(i=8;i>0;i--)
396C: MOVLW 08
396E: MOVLB 0
3970: MOVWF xFF
3972: MOVF xFF,F
3974: BTFSC FD8.2
3976: GOTO 398E
.................... { if(Bit_Mask&data)++Count_Of_Command_Bits;
397A: MOVLB 2
397C: MOVF x00,W
397E: MOVLB 0
3980: ANDWF xFE,W
3982: XORLW 00
3984: BTFSS FD8.2
3986: INCF xFD,F
.................... Bit_Mask<<1;
.................... }
3988: DECF xFF,F
398A: GOTO 3972
....................
.................... if(Count_Of_Command_Bits>1)
.................... { Bad_Data_Value=1;
398E: MOVF xFD,W
3990: SUBLW 01
3992: BTFSC FD8.0
3994: GOTO 39A2
3998: MOVLB 2
399A: BSF x01.1
.................... Comm1_Buffer[5]=0;
399C: MOVLB 5
399E: CLRF x05
39A0: MOVLB 0
.................... }
|
What I did uses more code space but runs ~5 times faster than a loop. I don't know what is the right way. I'm really not even sure I got your sugestion right Neil. |
|
![](templates/subSilver/images/spacer.gif) |
Douglas Kennedy
Joined: 07 Sep 2003 Posts: 755 Location: Florida
|
|
Posted: Tue Feb 17, 2004 10:15 am |
|
|
Just a crazy idea.... try a binary search for the expected single bits
1) is it in the left 4 bits or the right 4 bits?
test the nibble to see if not zero ( indicates presence of at least one bit)
not in both means error also in both means error
2) if set bits found in only in one of the nibbles split that nibble into 2 bits right 2 bits left
if in both 2bit sections means error
3) last but not least and assuming we got this far with out detecting an error test to see if it is 3 ...two bits set means error
I've always wanted to use swap for something other than saving regs in interrupts so lets go crazy
a test for 1) above
let the byte b also be equivalent to x*16+y x is left nibble y is right nibble
so swap(b) is y*16+x
if(b==0) goto error;
if((b>15 ) && (swap(b)>15)) goto error;
if(b>15) swap(b);///nibble is in right most 4 bits either way
a test for 2) above
if(((b&0x03)>0) && swap((b<<2))>15) goto error; // left and right bits are set
/// we have xx00 00xx
// with only 1100 0000 or 0000 0011 as the remaining errors
// dec 192 dec 3
now for test 3) above
if ((b==192 ) || (b==3) goto error;
/// its a winner only one bit was set
error:
/// it has none or more than one bit set
Hope this wasn't too crazy.
Last edited by Douglas Kennedy on Tue Feb 17, 2004 12:10 pm; edited 6 times in total |
|
![](templates/subSilver/images/spacer.gif) |
Guest Guest
|
|
Posted: Tue Feb 17, 2004 11:04 am |
|
|
what about this:
Code
data=Comm1_Buffer[5];
Count_Of_Command_Bits=1;
if(bit_test(data, 0)) Count_Of_Command_Bits--;
if(bit_test(data, 1)) Count_Of_Command_Bits--;
if(bit_test(data, 2)) Count_Of_Command_Bits--;
if(bit_test(data, 3)) Count_Of_Command_Bits--;
if(bit_test(data, 4)) Count_Of_Command_Bits--;
if(bit_test(data, 5)) Count_Of_Command_Bits--;
if(bit_test(data, 6)) Count_Of_Command_Bits--;
if(bit_test(data, 7)) Count_Of_Command_Bits--;
if(Count_Of_Command_Bits)
// this is an error as at least 2 bits are set
else
// OK only one bit is set |
|
![](templates/subSilver/images/spacer.gif) |
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|