I'm currently trying to understand the process of extracting specific bits within a binary sequence. During my research, I came across an algorithm I found online that utilizes the right shift operation along with the AND logical operation. However, I'm struggling to understand why the AND operation is essential in this context.

Take, example, the number 214 in binary (11010110). If my objective is to extract the higher nibble (the leftmost 4 bits), I can achieve this by performing a simple right shift of 4 positions, which results in the value 13 in binary (00001101) - precisely the higher nibble I'm looking for. In such cases, it seems that the AND operation is not necessary.

Could you kindly help why and when the AND operation becomes necessary in the process of bit extraction?

 

Your right shift requires four shifts.
AND operation is one instruction.

Suppose you wanted to extract the least significant four bits, how would you do it?
Suppose you wanted to extract bits 7, 6, and 3, you can do it with a single AND instruction.

 

In such cases, it seems that the AND operation is not necessary.

In such cases the AND operation is not necessary, but such cases are very specific. For more general bit extraction the AND operation serves as a mask to select specific bits.

 

I was referring to the algorithm mentioned from the online link, which is : 'Output = (uint8_t)((Data>>9) & 0x003F)

https://fastbitlab.com/microcontroller-embedded-c-programming-lecture-116-bit-extraction/

 

Let’s do your example again, but extract only bits 4 and 5:

Start with: 11010110
Shift right 4: 1101

So you have two extra bits you don’t want.

And with 3 (0011): 01

Which is the desired result. Your example only worked because there were no bits to the left of the ones you wanted.

 

I was referring to the algorithm mentioned from the online link, which is : 'Output = (uint8_t)((Data>>9) & 0x003F)

https://fastbitlab.com/microcontroller-embedded-c-programming-lecture-116-bit-extraction/

The order of operation is given by the parentheses. The shift operation takes place on a word of two bytes or more. The AND operation discards bits 7 & 6 from the low order byte, and all the bits from however many high order bytes there are. Then the result is cast to type uint8_t. You need to review your understanding of machine operations to clarify what is going on.

 

Let’s do your example again, but extract only bits 4 and 5:

Start with: 11010110
Shift right 4: 1101

So you have two extra bits you don’t want.

And with 3 (0011): 01

Which is the desired result. Your example only worked because there were no bits to the left of the ones you wanted.

I believe I've understood the point you're trying to convey. Take a look at the example below, which illustrates the process required to extract a specific bit from the higher nibble in one byte

In the sequence "11010110," when we extract bits 4, 5, and 6 in sequence, we obtain "101."

the result of "1101 & 101" is "101."

To extract bit 7 and bit 4 from the sequence "11010110,"

Thus, "1101 & 1001" obtain the result "1001.

 

I believe I've understood the point you're trying to convey. Take a look at the example below, which illustrates the process required to extract a specific bit from the higher nibble in one byte

In the sequence "11010110," when we extract bits 4, 5, and 6 in sequence, we obtain "101."

the result of "1101 & 101" is "101."

To extract bit 7 and bit 4 from the sequence "11010110,"

Thus, "1101 & 1001" obtain the result "1001.

You are making progress, but still have misunderstandings.

If you want to extract bits 4, 5, and 6, then you need a mask in which those bits are set, namely 01110000.

When you AND that with the data, you have "?abc????" & "01110000", which yields "0abc0000".

The purpose of the AND operation is to force the bits you aren't interested in to a 0, while preserving the value of the bits you ARE interested in.

 

Shifting first is often better because the constant is smaller, and many instruction sets can put them in an instruction, whereas it cannot put a full 8-bit constant and would need an extra instruction.

 

Shifting first is often better because the constant is smaller, and many instruction sets can put them in an instruction, whereas it cannot put a full 8-bit constant and would need an extra instruction.

Yep. Whether that's practical, of course, depends on the situation, including the capabilities of the hardware being used.

 

You are making progress, but still have misunderstandings.

I am still confused, I see three types of bit extraction examples.

Extracting a Single Bit:
Let's say we have the binary number 10110110, and we want to extract the 4th bit from the right (starting from 0). The 4th bit is 1.

Result = 0000 0001

Extracting a Range of Bits:
If we want to extract a range of bits, for example, bits 3 to 6 from the right in the binary number 11011010, we would get 1011. This involves extracting bits 3, 4, 5, and 6.

Result = 0001011

Extracting Specific Bits:
To extract specific bits, such as bit 7, bit 5, and bit 3 from the binary number 11011010.
So, the extracted bits are 101.

Result = 0000 0101

I am doubtful about the result I am obtaining. Please confirm if this is the correct result

 

Show your work

 

If your are looking for a specific bit, there is no need to shift or and, just use btfsc or btfss for comparison

If your dealing with multiple bits you want to "match" then you can use XORLW and look at the "Z" flag.

If you are dealing with a data stream from an I/O then you can AND the I/O pin with a mask, SUBLW with a "1", and shift the "C" flag directly into a BYTE for comparison.

 

I am still confused, I see three types of bit extraction examples.

Extracting a Single Bit:
Let's say we have the binary number 10110110, and we want to extract the 4th bit from the right (starting from 0). The 4th bit is 1.

Result = 0000 0001

Extracting a Range of Bits:
If we want to extract a range of bits, for example, bits 3 to 6 from the right in the binary number 11011010, we would get 1011. This involves extracting bits 3, 4, 5, and 6.

Result = 0001011

Extracting Specific Bits:
To extract specific bits, such as bit 7, bit 5, and bit 3 from the binary number 11011010.
So, the extracted bits are 101.

Result = 0000 0101

I am doubtful about the result I am obtaining. Please confirm if this is the correct result

Extracting a bit, or a set of bits, usually entails keeping those bits in their respective positions, unless there is some reason to shift them down to the right. So you need to make it clear what YOU mean by extracting a bit or bits.

If you DO mean that you want to shift them, then you need to shift them by an amount corresponding to the lowest numbered bit you want to extract. Logically, you can perform the shift either before or after the logical masking step. Depending on the compiler and the hardware, there can be performance considerations that favor one over the other -- if so, they likely favor doing the shift before the mask.

How you go about doing this depends on where you want the tradeoff between code readability/writability and performance. If performance is a driving factor, you need to take the hardware capabilities of your specific hardware into account, as well as how your specific compiler maps operations to that specific hardware.

 

If your are looking for a specific bit, there is no need to shift or and, just use btfsc or btfss for comparison

If your dealing with multiple bits you want to "match" then you can use XORLW and look at the "Z" flag.

If you are dealing with a data stream from an I/O then you can AND the I/O pin with a mask, SUBLW with a "1", and shift the "C" flag directly into a BYTE for comparison.

I wasn't aware that every processor was guaranteed to have these specific instructions.

Since the TS is referring to embedded C programming, how is he going to write his C code to do this?

 

I am still confused, I see three types of bit extraction examples.

Extracting a Single Bit:
Let's say we have the binary number 10110110, and we want to extract the 4th bit from the right (starting from 0). The 4th bit is 1.

Result = 0000 0001

Extracting a Range of Bits:
If we want to extract a range of bits, for example, bits 3 to 6 from the right in the binary number 11011010, we would get 1011. This involves extracting bits 3, 4, 5, and 6.

Result = 0001011

Extracting Specific Bits:
To extract specific bits, such as bit 7, bit 5, and bit 3 from the binary number 11011010.
So, the extracted bits are 101.

Result = 0000 0101

I am doubtful about the result I am obtaining. Please confirm if this is the correct result

By wanting to pack the extracted bits into the right side of the output, you are making matters considerably more complicated. Why do you want to do this?

 

A typical embedded C programming bit example:
Usually there is a register file for the controller.

/*
* C Header file for the Microchip PIC Microcontroller
* PIC16F18324
* */

One register section of the header. You would use these instead of 'magic' numbers for the required operations.

// Register: T0CON0
extern volatile unsigned char           T0CON0              @ 0x017;
#ifndef _LIB_BUILD
asm("T0CON0 equ 017h");
#endif
// bitfield definitions
typedef union {
    struct {
        unsigned T0OUTPS                :4;
        unsigned T016BIT                :1;
        unsigned T0OUT                  :1;
        unsigned                        :1;
        unsigned T0EN                   :1;
    };
    struct {
        unsigned T0OUTPS0               :1;
        unsigned T0OUTPS1               :1;
        unsigned T0OUTPS2               :1;
        unsigned T0OUTPS3               :1;
    };
} T0CON0bits_t;
extern volatile T0CON0bits_t T0CON0bits @ 0x017;
// bitfield macros
#define _T0CON0_T0OUTPS_POSN                                0x0
#define _T0CON0_T0OUTPS_POSITION                            0x0
#define _T0CON0_T0OUTPS_SIZE                                0x4
#define _T0CON0_T0OUTPS_LENGTH                              0x4
#define _T0CON0_T0OUTPS_MASK                                0xF
#define _T0CON0_T016BIT_POSN                                0x4
#define _T0CON0_T016BIT_POSITION                            0x4
#define _T0CON0_T016BIT_SIZE                                0x1
#define _T0CON0_T016BIT_LENGTH                              0x1
#define _T0CON0_T016BIT_MASK                                0x10
#define _T0CON0_T0OUT_POSN                                  0x5
#define _T0CON0_T0OUT_POSITION                              0x5
#define _T0CON0_T0OUT_SIZE                                  0x1
#define _T0CON0_T0OUT_LENGTH                                0x1
#define _T0CON0_T0OUT_MASK                                  0x20
#define _T0CON0_T0EN_POSN                                   0x7
#define _T0CON0_T0EN_POSITION                               0x7
#define _T0CON0_T0EN_SIZE                                   0x1
#define _T0CON0_T0EN_LENGTH                                 0x1
#define _T0CON0_T0EN_MASK                                   0x80
#define _T0CON0_T0OUTPS0_POSN                               0x0
#define _T0CON0_T0OUTPS0_POSITION                           0x0
#define _T0CON0_T0OUTPS0_SIZE                               0x1
#define _T0CON0_T0OUTPS0_LENGTH                             0x1
#define _T0CON0_T0OUTPS0_MASK                               0x1
#define _T0CON0_T0OUTPS1_POSN                               0x1
#define _T0CON0_T0OUTPS1_POSITION                           0x1
#define _T0CON0_T0OUTPS1_SIZE                               0x1
#define _T0CON0_T0OUTPS1_LENGTH                             0x1
#define _T0CON0_T0OUTPS1_MASK                               0x2
#define _T0CON0_T0OUTPS2_POSN                               0x2
#define _T0CON0_T0OUTPS2_POSITION                           0x2
#define _T0CON0_T0OUTPS2_SIZE                               0x1
#define _T0CON0_T0OUTPS2_LENGTH                             0x1
#define _T0CON0_T0OUTPS2_MASK                               0x4
#define _T0CON0_T0OUTPS3_POSN                               0x3
#define _T0CON0_T0OUTPS3_POSITION                           0x3
#define _T0CON0_T0OUTPS3_SIZE                               0x1
#define _T0CON0_T0OUTPS3_LENGTH                             0x1
#define _T0CON0_T0OUTPS3_MASK                               0x8
[code]

https://onlinedocs.microchip.com/pr/GUID-2AB01789-9FC2-4D02-AE67-727C4F9D3E47-en-US-3/index.html?GUID-D9BEFF1B-81BF-43C4-826D-5635F04F2E9E
Register Initialization using Bit Masks
[code=c]
T0CON0 = _T0CON0_T0EN_MASK       /* Enable TMR0 */
       | _T0CON0_T0OUTPS0_MASK   /* Select 1:10 postscaler */
       | _T0CON0_T0OUTPS3_MASK;
T0CON0 &= ~_T0CON0_T016BIT_MASK; /* Select 8-bit operation mode explicitly */

The POSITION defines can be used for bit shifting.

 

I wasn't aware that every processor was guaranteed to have these specific instructions.

Since the TS is referring to embedded C programming, how is he going to write his C code to do this?

Does C not have an XOR function? ... and can you not determine if a value is ZERO or not? When testing for a specific bit or multiple bits you XOR a mask with the bit or bits you want to test, and then you check if the result is ZERO or not ... if it is ZERO then the bit or bits tested were all 1's ... if not then the bit tested was a ZERO and if multiple bits were tested, then at least one was a ZERO.

Similar with AND'ing ... if you AND a mask with just one bit and the result is ZERO then the bit tested is a ZERO.... if the result is a ONE, then the bit tested is a ON.

Using 'sublw' is simply subtracting 1 from your result ... if your result is greater than ZERO subtracting 1 keeps the result positive. If the result is ZERO, then subtracting 1 will produce a negative value and in a micro controller a "C" carry Flag is thrown. In C, if the result is negative, that essentially is your carry flag. It is sometimes convenient to use the carry flag like this because yo can shift it directly into a variable, forming a BYTE of the incoming data.

 

The C compiler can be designed to accommodate the least common denominator of all MCU instruction sets. If the MCU has bit addressing capabilities then these special instructions and be implemented in specific MCU header files.

In general, AND and SHIFT MCU logical functions are enough to implement any random arrangement of bit instructions.

Heck, we wrote bit operations on a PDP-8/S minicomputer and you cannot get a more primitive CPU instruction set than that.

 

Does C not have an XOR function? ... and can you not determine if a value is ZERO or not? When testing for a specific bit or multiple bits you XOR a mask with the bit or bits you want to test, and then you check if the result is ZERO or not ... if it is ZERO then the bit or bits tested were all 1's ... if not then the bit tested was a ZERO and if multiple bits were tested, then at least one was a ZERO.

Similar with AND'ing ... if you AND a mask with just one bit and the result is ZERO then the bit tested is a ZERO.... if the result is a ONE, then the bit tested is a ON.

Using 'sublw' is simply subtracting 1 from your result ... if your result is greater than ZERO subtracting 1 keeps the result positive. If the result is ZERO, then subtracting 1 will produce a negative value and in a micro controller a "C" carry Flag is thrown. In C, if the result is negative, that essentially is your carry flag. It is sometimes convenient to use the carry flag like this because yo can shift it directly into a variable, forming a BYTE of the incoming data.

Yes, C has a bitwise XOR, but that is not what you told the TS to use, you told him to use a small laundry list of assembly instructions, namely {btfsc, btfss, XORLW, and SUBLW}. In addition, you told him to dink around with the Z and C flags. None of this is within the realm of embedded C -- the purpose of a high-level language is to abstract away these low level instructions that are typically very specific to certain families of processors (these sound like PIC instructions to me).

As for the suggestion you make here:

When testing for a specific bit or multiple bits you XOR a mask with the bit or bits you want to test, and then you check if the result is ZERO or not ... if it is ZERO then the bit or bits tested were all 1's ... if not then the bit tested was a ZERO and if multiple bits were tested, then at least one was a ZERO.

Think about this. When you XOR some of the bits in a register with a mask containing a 1 at the location of the bits you want to test, those bits will be inverted. But, more importantly, the bits you are NOT testing will be left unchanged and must be assumed to be a combination of 0s and 1s. You claim that if the result is not zero that at least one of the bits of tested was a zero. But what if all of the bits being tested were 1 but so was one of the bits not being tested?

In C, if the result is negative, that essentially is your carry flag.

The problem with this is that if you are bit-banging in C, you should be using unsigned data types and, hence, any result of subtraction is nonnegative. This is a trick that can be used safely in assembly because, at that level, there is seldom a distinction between data types -- it's the code that establishes what type of data it is treated as. The reason you should use unsigned types is because the behavior of some logical operations is implementation-defined or even undefined for signed integers. Now, if you happen to be using a compiler in which the compiler specifies these behaviors, then you can write code to leverage those specs -- but that code is not locked to that version of that compiler, something that should be avoided whenever possible.