Creating A Byte (8 Bits) From 4 2 Bits - Stack Overflow

Just browsing Stack Overflow? Help us improve your experience. Sign up for research

1. 1. Home
   2. Questions
   3. Tags
   4. Users
   5. Companies
   6. Labs
   7. Jobs
   8. Discussions
   9. Collectives

   10. Communities for your favorite technologies. Explore all Collectives

2. Teams

   Ask questions, find answers and collaborate at work with Stack Overflow for Teams.

   Try Teams for free Explore Teams
3. Teams

4. Ask questions, find answers and collaborate at work with Stack Overflow for Teams. Explore Teams

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Learn more about Collectives

Teams

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Learn more about Teams

Get early access and see previews of new features.

Learn more about Labs Creating a byte (8 bits) from 4 2 bits Ask Question Asked 10 years, 10 months ago Modified 10 years, 10 months ago Viewed 934 times 1

I am trying to figure out a way to get as much out of the limited memory in my microcontroller (32kb) and am seeking suggestions or pointers to an algorithm that performs what I am attempting to do.

Some background: I am sending Manchester Encoded bits out a SPI (Serial Peripheral Interface) directly from DMA. As the smallest possible unit I can store data into DMA is a byte (8 bits), I am having to represent my 1's as 0b11110000 and my 0's as 0b00001111. This basically means that for every bit of information, I need to use a byte (8 bits) of memory. Which is very inefficient.

If I could reduce this, so that my 1's are represented as 0b10 and my 0's as 0b01, I'd only have to use a 1/4 of a byte (2 bits) for every 1 bit of memory, which is fine for my solution.

Now, if I could save to DMA in bits, this would not be a problem, but of course I need to work with bytes. So I know the solution to my problem involves collecting the 8 bits (or in my case, 4 2bits) and then storing to DMA as a byte.

Questions:

Is there a standard way to solve this problem?

How can I some how create a 8 bit number from a collection of 4 2 bit numbers? But I do not want the addition of these numbers, but the actual way it looks when collected together.

For example: I have the following 4 2 bit numbers (keeping in mind that 0b10 represents 1 and 0b01 represents 0) (Also, the type these are stored in is open to the solution, as obviously there is no such thing as a 2 bit type)

Number1: 0b01 Number 2: 0b10 Number 3: 0b10 Number4: 0b01

And I want to create the following 8 bit number from these:

8 Bit Number: 0b01 10 10 01 or without the spaces 0b01101001 (0x69)

I am programming in c

• c
• algorithm
• binary
• spi
• dma

Share Improve this question Follow asked Jan 23, 2014 at 0:27 Remixed123Remixed123 1,58544 gold badges2121 silver badges3535 bronze badges 0 Add a comment |

3 Answers 3

Sorted by: Reset to default Highest score (default) Trending (recent votes count more) Date modified (newest first) Date created (oldest first) 1

It seems that you can pack four numbers a, b, c, d, all of which of value zero or one, like so:

64 * (a + 1) + 16 * (b + 1) + 4 * (c + 1) + (d + 1)

This is using the fact that x + 1 encodes your two-bit integer: 1 becomes 0b10, and 0 becomes 0b01.

Share Improve this answer Follow answered Jan 23, 2014 at 0:34 Kerrek SBKerrek SB 476k9393 gold badges895895 silver badges1.1k1.1k bronze badges 4

• 2 I feel like a bit-shift implementation would be more clear: (a + 1)<<6 + (b + 1)<<4 + (c + 1)<<2 + (d + 1) – Macattack Commented Jan 23, 2014 at 0:45
• How did you answer this question so quickly? Amazed and thankful, you may have just helped me reduce my memory usage by a factor of 4! – Remixed123 Commented Jan 23, 2014 at 0:49
• Thanks Macattack, feel free to add this as an answer, and which ever one I use I will aware the tick. Apologies Kerrek, I jumped the gun on the tick...but still impressed with your speed! – Remixed123 Commented Jan 23, 2014 at 0:53
• 1 Great, but you can go one better! Do all the additions in parallel: ((((a << 2) | b) << 2) | c) << 2) | d) + 0x55 Shifting by only 2 each time runs faster if the processor doesn't have a barrel shifter. – Gene Commented Jan 23, 2014 at 2:04

Add a comment | 1

It's Manchester encoding so 0b11110000 and 0b00001111 should be the only candidates. If so, then reduce the memory by a factor of 8.

uint8_t PackedByte = 0; for (i=0; i<8; i++) { PackedByte <<= 1; if (buf[i] == 0xF0) // 0b11110000 PackedByte++; }

Other other hand, if it's Manchester encoding and one may not have perfect encoding, then there are 3 results: 0, 1, indeterminate.

uint8_t PackedByte = 0; for (i=0; i<8; i++) { int upper = BitCount(buf[i] >> 4); int lower = BitCount(buf[i] & 0xF); if (upper > lower) PackedByte++; else if (upper == lower) Hande_Indeterminate(); }

Various simplifications absent in the above, but shown for logic flow.

Share Improve this answer Follow edited Jan 23, 2014 at 2:09 answered Jan 23, 2014 at 1:45 chuxchux 153k1515 gold badges144144 silver badges285285 bronze badges 5

• Hi Chux, not sure I understand how this works, since I need a rising edge to represent 0 and a falling edge to represent 1. How do I represent this with 1 bit with Manchester encoding? – Remixed123 Commented Jan 23, 2014 at 2:26
• @Remixed123 Excuse me. My answer is focused on receiving rather than transmitting. I still think you can use 1 packed bit to instruct the SPI's next 8 bits, as 0b11110000 or ob00001111. The larger challenge is in reading the SPI with the idea the data in Manchester encoded. You are doing a 4x oversample on sending. If you are also receiving likewise, this answer may help. – chux Commented Jan 23, 2014 at 2:43
• That would be great if I could use 1 bit to instruct my SPI's next eight bits. Not sure that my microcontroller has that level of SPI configurability. Does this feature have a name? That way I can search on it in the data sheet for my microcontroller. Regarding the receiving end, this is a bunch of (up to 2048) individually self addressed integrated circuits. They each take a portion of the packet and pass the rest on. – Remixed123 Commented Jan 23, 2014 at 2:49
• No. What I suggest to send is that in your buffer of data to send, you extract 1 bit at a time and then send to the SPI an 8-bit byte of 0b11110000 or 0b00001111. If you can not tell the SPI 8-bits at a time, set up a local buffer of 8 and each time you need to send a bit, pull from there, replenishing that 8-bit buffer with 0b11110000 or 0b00001111 as needed based on the next bit from the data buffer. – chux Commented Jan 23, 2014 at 2:55
• Ok, actually that's an interesting approach. I'd need to see if the data can be sent without breaking the communication or timing in anyway. Might be possible to get timing right by setting up a timer, but getting it to send in one constant stream without any breaks might be difficult. – Remixed123 Commented Jan 23, 2014 at 3:15

Add a comment | 1

To number get abcd from (a,b,c,d) you need to shift the number to their places and OR :-

(a<<6)|(b<<4)|(c<<2)|d

Share Improve this answer Follow answered Jan 23, 2014 at 6:12 Vikram BhatVikram Bhat 6,23633 gold badges2121 silver badges1919 bronze badges Add a comment |

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Thanks for contributing an answer to Stack Overflow!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.
• Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

Draft saved Draft discarded

Sign up or log in

Sign up using Google Sign up using Email and Password Submit

Post as a guest

Name Email

Required, but never shown

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged

• c
• algorithm
• binary
• spi
• dma

or ask your own question.

• Featured on Meta
• We’re (finally!) going to the cloud!
• More network sites to see advertising test [updated with phase 2]

Related

0 How to make 1 byte from 8 bit samples in java or c? 1 How to break a byte into 4 pairs of 2 bits 0 Decode FOUR_BITS of a byte in a byte array (in C) 0 Splitting 3 bytes into six 4 bits and recombining to two 12 bits 0 Converting 4 bytes to unsigned int 1 Convert a byte to 8 booleans 1 How can I split binary into 4 bytes sections? 2 converting integer into 4 bit binary 1 Interleave 4 byte ints to 8 byte int 0 How to convert 4 bytes hex to decimal manually

Hot Network Questions

• Diagonal analogue of symmetric functions
• Where can I find an up-to-date map of Stockholm Central Station that shows the platform layout?
• How to Prove This Elegant Integral Identity Involving Trigonometric and Square Root Terms
• If the hard problem of consciousness is unanswerable, is it a hard problem or just a bad question?
• Why did Satan take Jesus to the Temple to jump down from?
• What are the pros & cons of downdraft ventilation?
• Why does water vapor sometimes start to twirl above a pot of boiling water?
• How do I remove a hat from my horse?
• How do I report to Springer a scientific fraud to a cryptographic paper published in Springer?
• When and how were nets and filters first shown to be equivalent?
• Who are Catalina and Teresa in Gabriela Mistral's poem Vieja?
• What is the name of the lady with the white blouse?
• Why is MacBook Air trackpad spanning to completely separate system?
• Does Naomi Nagata go to her grave thinking that she killed her son?
• Find the one sentence that is wrong in the following proof.
• Typesetting phantom contents in nicematrix
• Difference between English short stories and short English stories
• What happened to the lifeboats in Star Trek: First Contact?
• What does "inside" refer to when we say that the electric field inside a conductor is 0?
• will "brown aluminum" drip-edge suffer galvanic corrosion if it rests against fascia made of copper-treated lumber?
• How to distinguish interaction from mediation?
• Can I use the Wish Spell to change my Class ( Wizard 18, Warlock 2 to Wizard 19, Warlock 1)?
• List of all sequences with certain properties
• The sum of multiple irrational numbers can be rational, even when they're not conjugates. Is this normal?

more hot questions Question feed Subscribe to RSS Question feed

To subscribe to this RSS feed, copy and paste this URL into your RSS reader.

lang-c