Reputation: 5733
In C/C++ what's the simplest way to reverse the order of bits in a byte?
While there are multiple ways to reverse bit order in a byte, I'm curious as to what is the "simplest" for a developer to implement. And by reversing I mean:
1110 -> 0111
0010 -> 0100
This is similar to, but not a duplicate of this PHP question.
This is similar to, but not a duplicate of this C question. This question is asking for the easiest method to implement by a developer. The "Best Algorithm" is concerned with memory and cpu performance.
Upvotes: 168
Views: 305349
Answers (30)
Reputation: 19
This is simple and fast:
unsigned char reverse(unsigned char rv)
{
unsigned char tmp=0;
if( rv&0x01 ) tmp = 0x80;
if( rv&0x02 ) tmp |= 0x40;
if( rv&0x04 ) tmp |= 0x20;
if( rv&0x08 ) tmp |= 0x10;
if( rv&0x10 ) tmp |= 0x08;
if( rv&0x20 ) tmp |= 0x04;
if( rv&0x40 ) tmp |= 0x02;
if( rv&0x80 ) tmp |= 0x01;
return tmp;
}
Upvotes: 0
Reputation: 43
uint32_t ReverseBits(uint32_t num)
{
uint32_t result = 0;
uint8_t counter = 32 * (!!num); /* read Eric Postpischil's comment */
while(num)
{
result <<= 1;
result |= (num & 1);
num >>= 1;
--counter;
}
return result << counter;
}
Upvotes: -2
Reputation: 2475
Some of you might like this fairly clean-looking function. Pure C, easily adapted to any integer size.
unsigned int reverse(unsigned int b, int n) {
unsigned int r = 0; // Result
for (int i = 0; i < n; i++) {
r <<= 1;
r |= b & 1;
b >>= 1;
}
return r;
}
Upvotes: -1
Reputation: 11259
There are many ways to reverse bits depending on what you mean the "simplest way".
Reverse by Rotation
Probably the most logical, consists in rotating the byte while applying a mask on the first bit (n & 1):
unsigned char reverse_bits(unsigned char b)
{
unsigned char r = 0;
unsigned byte_len = 8;
while (byte_len--) {
r = (r << 1) | (b & 1);
b >>= 1;
}
return r;
}
As the length of an unsigner char is 1 byte, which is equal to 8 bits, it means we will scan each bit
while (byte_len--)We first check if b as a bit on the extreme right with
(b & 1); if so we set bit 1 on r with|and move it just 1 bit to the left by multiplying r by 2 with(r << 1)Then we divide our unsigned char b by 2 with
b >>=1to erase the bit located at the extreme right of variable b. As a reminder, b >>= 1; is equivalent to b /= 2;
Reverse in One Line
This solution is attributed to Rich Schroeppel in the Programming Hacks section
unsigned char reverse_bits3(unsigned char b)
{
return (b * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff;
}
The multiply operation (b * 0x0202020202ULL) creates five separate copies of the 8-bit byte pattern to fan-out into a 64-bit value.
The AND operation (& 0x010884422010ULL) selects the bits that are in the correct (reversed) positions, relative to each 10-bit groups of bits.
Together the multiply and the AND operations copy the bits from the original byte so they each appear in only one of the 10-bit sets. The reversed positions of the bits from the original byte coincide with their relative positions within any 10-bit set.
The last step (% 0x3ff), which involves modulus division by 2^10 - 1 has the effect of merging together each set of 10 bits (from positions 0-9, 10-19, 20-29, ...) in the 64-bit value. They do not overlap, so the addition steps underlying the modulus division behave like OR operations.
Divide and Conquer Solution
unsigned char reverse(unsigned char b) {
b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
return b;
}
This is the most upvoted answer and despite some explanations, I think that for most people it feels difficult to visualize whats 0xF0, 0xCC, 0xAA, 0x0F, 0x33 and 0x55 truly means.
It does not take advantage of '0b' which is a GCC extension and is included since the C++14 standard, release in December 2014, so a while after this answer dating from April 2010
Integer constants can be written as binary constants, consisting of a sequence of ‘0’ and ‘1’ digits, prefixed by ‘0b’ or ‘0B’. This is particularly useful in environments that operate a lot on the bit level (like microcontrollers).
Please check below code snippets to remember and understand even better this solution where we move half by half:
unsigned char reverse(unsigned char b) {
b = (b & 0b11110000) >> 4 | (b & 0b00001111) << 4;
b = (b & 0b11001100) >> 2 | (b & 0b00110011) << 2;
b = (b & 0b10101010) >> 1 | (b & 0b01010101) << 1;
return b;
}
NB: The >> 4 is because there are 8 bits in 1 byte, which is an unsigned char so we want to take the other half, and so on.
We could easily apply this solution to 4 bytes with only two additional lines and following the same logic. Since both mask complement each other we can even use ~ in order to switch bits and saving some ink:
uint32_t reverse_integer_bits(uint32_t b) {
uint32_t mask = 0b11111111111111110000000000000000;
b = (b & mask) >> 16 | (b & ~mask) << 16;
mask = 0b11111111000000001111111100000000;
b = (b & mask) >> 8 | (b & ~mask) << 8;
mask = 0b11110000111100001111000011110000;
b = (b & mask) >> 4 | (b & ~mask) << 4;
mask = 0b11001100110011001100110011001100;
b = (b & mask) >> 2 | (b & ~mask) << 2;
mask = 0b10101010101010101010101010101010;
b = (b & mask) >> 1 | (b & ~mask) << 1;
return b;
}
[C++ Only] Reverse Any Unsigned (Template)
The above logic can be summarized with a loop that would work on any type of unsigned:
template <class T>
T reverse_bits(T n) {
short bits = sizeof(n) * 8;
T mask = ~T(0); // equivalent to uint32_t mask = 0b11111111111111111111111111111111;
while (bits >>= 1) {
mask ^= mask << (bits); // will convert mask to 0b00000000000000001111111111111111;
n = (n & ~mask) >> bits | (n & mask) << bits; // divide and conquer
}
return n;
}
C++ 17 only
You may use a table that store the reverse value of each byte with (i * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff, initialized through a lambda (you will need to compile it with g++ -std=c++1z since it only works since C++17), and then return the value in the table will give you the accordingly reversed bit:
#include <cstdint>
#include <array>
uint8_t reverse_bits(uint8_t n) {
static constexpr array<uint8_t, 256> table{[]() constexpr{
constexpr size_t SIZE = 256;
array<uint8_t, SIZE> result{};
for (size_t i = 0; i < SIZE; ++i)
result[i] = (i * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff;
return result;
}()};
return table[n];
}
main.cpp
Try it yourself with inclusion of above function:
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
template <class T>
void print_binary(T n)
{ T mask = 1ULL << ((sizeof(n) * 8) - 1); // will set the most significant bit
for(; mask != 0; mask >>= 1) putchar('0' | !!(n & mask));
putchar('\n');
}
int main() {
uint32_t n = 12;
print_binary(n);
n = reverse_bits(n);
print_binary(n);
unsigned char c = 'a';
print_binary(c);
c = reverse_bits(c);
print_binary(c);
uint16_t s = 12;
print_binary(s);
s = reverse_bits(s);
print_binary(s);
uint64_t l = 12;
print_binary(l);
l = reverse_bits(l);
print_binary(l);
return 0;
}
Reverse with asm volatile
Last but not least, if simplest means fewer lines, why not give a try to inline assembly?
You can test below code snippet by adding -masm=intel when compiling:
unsigned char reverse_bits(unsigned char c) {
__asm__ __volatile__ (R"(
mov cx, 8
daloop:
ror di
adc ax, ax
dec cx
jnz short daloop
;)");
}
Explanations line by line:
mov cx, 8 ; we will reverse the 8 bits contained in one byte
daloop: ; while loop
shr di ; Shift Register `di` (containing value of the first argument of callee function) to the Right
rcl ax ; Rotate Carry Left: rotate ax left and add the carry from shr di, the carry is equal to 1 if one bit was "lost" from previous operation
dec cl ; Decrement cx
jnz short daloop; Jump if cx register is Not equal to Zero, else end loop and return value contained in ax register
Upvotes: 43
Reputation: 4367
I find the following solution simpler than the other bit fiddling algorithms I've seen in here.
unsigned char reverse_byte(char a)
{
return ((a & 0x1) << 7) | ((a & 0x2) << 5) |
((a & 0x4) << 3) | ((a & 0x8) << 1) |
((a & 0x10) >> 1) | ((a & 0x20) >> 3) |
((a & 0x40) >> 5) | ((a & 0x80) >> 7);
}
It gets every bit in the byte, and shifts it accordingly, starting from the first to the last.
Explanation:
((a & 0x1) << 7) //get first bit on the right and shift it into the first left position
| ((a & 0x2) << 5) //add it to the second bit and shift it into the second left position
//and so on
Upvotes: 14
Reputation: 9
The easiest and fast way is with while
#define REVERSE_NUMBER(n, res) while (n) \
{ res = (res << 1) + (n % 2); n >>= 1; }
unsigned int res; //res is result
unsigned int n = 0x135F; // n = 1001101011111
REVERSE_NUMBER(n, res); // res = 1111101011001 (1F59)
or with function
unsigned int reverse_number(unsigned int n) {
unsigned int res;
while (n) {
res = (res << 1) + (n % 2);
n >>= 1;
}
return res;
}
even easier way and effective
// shift << and >> equivalent to multiplication and division by 2
// and bitwise & 1 equivalent mod by 2
unsigned int reverse_number(unsigned int n) {
unsigned int res = 0;
size_t i = sizeof(unsigned int) * 8; // 32 bit value
while (i--) {
res = (res << 1) + (n & 1); n >>= 1;
}
return res;
}
Upvotes: -1
Reputation: 71
If there is one wondering how to get uint16_t or uint32_t bit reversed by using the solution from Rich Schroeppel in the Programming Hacks section
unsigned char reverse_bits3(unsigned char b)
{
return (b * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff;
}
It can be done by following divide-and-conquer code on X86/X64 platform (little-endian):
uint16_t reverse_bits3(uint16_t s)
{
uint8_t &b0 = ((uint8_t*)&s)[0];
uint8_t &b1 = ((uint8_t*)&s)[1];
return (((uint16_t)reverse_bits3(b0))<<8) + reverse_bits3(b1);
}
uint32_t reverse_bits3(uint32_t u)
{
uint16_t &s0 = ((uint16_t*)&u)[0];
uint16_t &s1 = ((uint16_t*)&u)[1];
return (((uint16_t)reverse_bits3(s0))<<16) + reverse_bits3(s1);
}
Upvotes: 2
Reputation: 169
This is the easiest approach to remember to me as a developer:
unsigned char reverse_bits(unsigned char octet)
{
return (((octet >> 0) & 1) << 7) | \
(((octet >> 1) & 1) << 6) | \
(((octet >> 2) & 1) << 5) | \
(((octet >> 3) & 1) << 4) | \
(((octet >> 4) & 1) << 3) | \
(((octet >> 5) & 1) << 2) | \
(((octet >> 6) & 1) << 1) | \
(((octet >> 7) & 1) << 0);
}
Upvotes: 1
Reputation: 2915
With the help of various online resources, i jotted these for myself (not sure if they're 100% accurate) :
# octal hex
# bit-orig : 01234567 01234567:89ABCDEF
# bit-invert : 76543210 FEDCBA98:76543210
#
# clz : 32110000 43221111:00000000
# clo/ffs : 00001123 00000000:11112234
bit-reverse :
[ 0 4 2 6 1 5 3 7 ][084C2A6E195D3B7F]
# cto : 01020103 01020103:01020104
# ctz : 30102010 40102010:30102010
but this is mostly only convenient if your input is already either hex or octal.
In both formats (8 or 16), you'll notice that after the bit-reflections, all the even number indices are all on the first half. I've also highlighted the same 0-7 on the hex side to help with the visualization of it.
in fact, one doesn't even have to do a double substring. The lookup string can be either used as seeking the letter needed, or simply use it as an index lookup. this is how i reflect the CRC32 polynomial myself :
(z is the input polynomial (or just any hex string)
xn = 0 ^ (x = length(z)); # initialize to numeric 0,
# foo^bar in awk means
# foo-to-bar-th-power.
# same as foo**bar in other langs
y = substr(_REF_bitREV_hex, 2); # by pre-trimming the lookup str,
# it allows skipping the + 1 at
# every cycle of the loop
do {
xn *= 16
xn += index(y, substr(z,x,1)) # keep in mind that this is awk syntax,
# where strings start at index-1, not zero.
} while ( 1 < x—- );
One advantage of using a hex- or octal- based approach is that it allows for inputs of any length, enabling arbitrary precision operation without having to use a proper BigInteger or BigFloat library. For that, you'll have to substring out the new digit/letter and do string concats instead of simply adding each time.
Upvotes: 1
Reputation: 453
This is a similar method to sth's excellent answer, but with optimizations, support for up to 64-bit integers, and other small improvements.
I utilize a C++ template function reverse_bits() to let the compiler optimize for various word sizes of integers which might be passed to the function. The function should work correctly with any word size that is a multiple of 8 bits, up to a maximum of 64 bits. If your compiler supports words longer than 64 bits, the method is straightforward to extend.
This a complete, ready-to-compile example with the requisite headers. There is a convenient template function to_binary_str() for creating a std::string representation of binary numbers, along with a few calls with various word sizes to demonstrate everything.
If you remove the comments and blank lines, the function is quite compact and visually pleasing.
You can try out it on labstack here.
// this is the only header used by the reverse_bits() function
#include <type_traits>
// these headers are only used by demonstration code
#include <string>
#include <iostream>
#include <cstdint>
template<typename T>
T reverse_bits( T n ) {
// we force the passed-in type to its unsigned equivalent, because C++ may
// perform arithmetic right shift instead of logical right shift, depending
// on the compiler implementation.
typedef typename std::make_unsigned<T>::type unsigned_T;
unsigned_T v = (unsigned_T)n;
// swap every bit with its neighbor
v = ((v & 0xAAAAAAAAAAAAAAAA) >> 1) | ((v & 0x5555555555555555) << 1);
// swap every pair of bits
v = ((v & 0xCCCCCCCCCCCCCCCC) >> 2) | ((v & 0x3333333333333333) << 2);
// swap every nybble
v = ((v & 0xF0F0F0F0F0F0F0F0) >> 4) | ((v & 0x0F0F0F0F0F0F0F0F) << 4);
// bail out if we've covered the word size already
if( sizeof(T) == 1 ) return v;
// swap every byte
v = ((v & 0xFF00FF00FF00FF00) >> 8) | ((v & 0x00FF00FF00FF00FF) << 8);
if( sizeof(T) == 2 ) return v;
// etc...
v = ((v & 0xFFFF0000FFFF0000) >> 16) | ((v & 0x0000FFFF0000FFFF) << 16);
if( sizeof(T) <= 4 ) return v;
v = ((v & 0xFFFFFFFF00000000) >> 32) | ((v & 0x00000000FFFFFFFF) << 32);
// explictly cast back to the original type just to be pedantic
return (T)v;
}
template<typename T>
std::string to_binary_str( T n ) {
const unsigned int bit_count = sizeof(T)*8;
char s[bit_count+1];
typedef typename std::make_unsigned<T>::type unsigned_T;
unsigned_T v = (unsigned_T)n;
for( int i = bit_count - 1; i >= 0; --i ) {
if( v & 1 )
s[i] = '1';
else
s[i] = '0';
v >>= 1;
}
s[bit_count] = 0; // string null terminator
return s;
}
int main() {
{
char x = 0xBA;
std::cout << to_binary_str( x ) << std::endl;
char y = reverse_bits( x );
std::cout << to_binary_str( y ) << std::endl;
}
{
short x = 0xAB94;
std::cout << to_binary_str( x ) << std::endl;
short y = reverse_bits( x );
std::cout << to_binary_str( y ) << std::endl;
}
{
uint64_t x = 0xFEDCBA9876543210;
std::cout << to_binary_str( x ) << std::endl;
uint64_t y = reverse_bits( x );
std::cout << to_binary_str( y ) << std::endl;
}
return 0;
}
Upvotes: 2
Reputation: 229864
This should work:
unsigned char reverse(unsigned char b) {
b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
return b;
}
First the left four bits are swapped with the right four bits. Then all adjacent pairs are swapped and then all adjacent single bits. This results in a reversed order.
Upvotes: 317
Reputation: 61
If you using small microcontroller and need high speed solution with small footprint, this could be solutions. It is possible to use it for C project, but you need to add this file as assembler file *.asm, to your C project. Instructions: In C project add this declaration:
extern uint8_t byte_mirror(uint8_t);
Call this function from C
byteOutput= byte_mirror(byteInput);
This is the code, it is only suitable for 8051 core. In the CPU register r0 is data from byteInput. Code rotate right r0 cross carry and then rotate carry left to r1. Repeat this procedure 8 times, for every bit. Then the register r1 is returned to c function as byteOutput. In 8051 core is only posibble to rotate acumulator a.
NAME BYTE_MIRROR
RSEG RCODE
PUBLIC byte_mirror //8051 core
byte_mirror
mov r3,#8;
loop:
mov a,r0;
rrc a;
mov r0,a;
mov a,r1;
rlc a;
mov r1,a;
djnz r3,loop
mov r0,a
ret
PROS: It is small footprint, it is high speed CONS: It is not reusable code, it is only for 8051
011101101->carry
101101110<-carry
Upvotes: 1
Reputation: 405
This one helped me with 8x8 dot matrix set of arrays.
uint8_t mirror_bits(uint8_t var)
{
uint8_t temp = 0;
if ((var & 0x01))temp |= 0x80;
if ((var & 0x02))temp |= 0x40;
if ((var & 0x04))temp |= 0x20;
if ((var & 0x08))temp |= 0x10;
if ((var & 0x10))temp |= 0x08;
if ((var & 0x20))temp |= 0x04;
if ((var & 0x40))temp |= 0x02;
if ((var & 0x80))temp |= 0x01;
return temp;
}
Upvotes: 0
Reputation: 485
Assuming that your compiler allows unsigned long long:
unsigned char reverse(unsigned char b) {
return (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
}
Upvotes: 2
Reputation: 7925
I know that this question is dated but I still think that the topic is relevant for some purposes, and here is a version that works very well and is readable. I can not say that it is the fastest or the most efficient, but it ought to be one of the cleanest. I have also included a helper function for easily displaying the bit patterns. This function uses some of the standard library functions instead of writing your own bit manipulator.
#include <algorithm>
#include <bitset>
#include <exception>
#include <iostream>
#include <limits>
#include <string>
// helper lambda function template
template<typename T>
auto getBits = [](T value) {
return std::bitset<sizeof(T) * CHAR_BIT>{value};
};
// Function template to flip the bits
// This will work on integral types such as int, unsigned int,
// std::uint8_t, 16_t etc. I did not test this with floating
// point types. I chose to use the `bitset` here to convert
// from T to string as I find it easier to use than some of the
// string to type or type to string conversion functions,
// especially when the bitset has a function to return a string.
template<typename T>
T reverseBits(T& value) {
static constexpr std::uint16_t bit_count = sizeof(T) * CHAR_BIT;
// Do not use the helper function in this function!
auto bits = std::bitset<bit_count>{value};
auto str = bits.to_string();
std::reverse(str.begin(), str.end());
bits = std::bitset<bit_count>(str);
return static_cast<T>( bits.to_ullong() );
}
// main program
int main() {
try {
std::uint8_t value = 0xE0; // 1110 0000;
std::cout << +value << '\n'; // don't forget to promote unsigned char
// Here is where I use the helper function to display the bit pattern
auto bits = getBits<std::uint8_t>(value);
std::cout << bits.to_string() << '\n';
value = reverseBits(value);
std::cout << +value << '\n'; // + for integer promotion
// using helper function again...
bits = getBits<std::uint8_t>(value);
std::cout << bits.to_string() << '\n';
} catch(const std::exception& e) {
std::cerr << e.what();
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
And it gives the following output.
224
11100000
7
00000111
Upvotes: 0
Reputation: 17254
For the very limited case of constant, 8-bit input, this method costs no memory or CPU at run-time:
#define MSB2LSB(b) (((b)&1?128:0)|((b)&2?64:0)|((b)&4?32:0)|((b)&8?16:0)|((b)&16?8:0)|((b)&32?4:0)|((b)&64?2:0)|((b)&128?1:0))
I used this for ARINC-429 where the bit order (endianness) of the label is opposite the rest of the word. The label is often a constant, and conventionally in octal.
Here's how I used it to define a constant, because the spec defines this label as big-endian 205 octal.
#define LABEL_HF_COMM MSB2LSB(0205)
More examples:
assert(0b00000000 == MSB2LSB(0b00000000));
assert(0b10000000 == MSB2LSB(0b00000001));
assert(0b11000000 == MSB2LSB(0b00000011));
assert(0b11100000 == MSB2LSB(0b00000111));
assert(0b11110000 == MSB2LSB(0b00001111));
assert(0b11111000 == MSB2LSB(0b00011111));
assert(0b11111100 == MSB2LSB(0b00111111));
assert(0b11111110 == MSB2LSB(0b01111111));
assert(0b11111111 == MSB2LSB(0b11111111));
assert(0b10101010 == MSB2LSB(0b01010101));
Upvotes: 7
Reputation: 872
This is an old question, but nobody seems to have shown the clear easy way (the closest was edW). I used C# to test this, but there's nothing in this example that couldn't be done easily in C.
void PrintBinary(string prompt, int num, int pad = 8)
{
Debug.WriteLine($"{prompt}: {Convert.ToString(num, 2).PadLeft(pad, '0')}");
}
int ReverseBits(int num)
{
int result = 0;
int saveBits = num;
for (int i = 1; i <= 8; i++)
{
// Move the result one bit to the left
result = result << 1;
//PrintBinary("saveBits", saveBits);
// Extract the right-most bit
var nextBit = saveBits & 1;
//PrintBinary("nextBit", nextBit, 1);
// Add our extracted bit to the result
result = result | nextBit;
//PrintBinary("result", result);
// We're done with that bit, rotate it off the right
saveBits = saveBits >> 1;
//Debug.WriteLine("");
}
return result;
}
void PrintTest(int nextNumber)
{
var result = ReverseBits(nextNumber);
Debug.WriteLine("---------------------------------------");
PrintBinary("Original", nextNumber);
PrintBinary("Reverse", result);
}
void Main()
{
// Calculate the reverse for each number between 1 and 255
for (int x = 250; x < 256; x++)
PrintTest(x);
}
Upvotes: -3
Reputation: 145297
Here is a simple and readable solution, portable to all conformant platforms, including those with sizeof(char) == sizeof(int):
#include <limits.h>
unsigned char reverse(unsigned char c) {
int shift;
unsigned char result = 0;
for (shift = 0; shift < CHAR_BIT; shift++) {
result <<= 1;
result |= c & 1;
c >>= 1;
}
return result;
}
Upvotes: 3
Reputation: 1420
I'll chip in my solution, since i can't find anything like this in the answers so far. It is a bit overengineered maybe, but it generates the lookup table using C++14 std::index_sequence in compile time.
#include <array>
#include <utility>
constexpr unsigned long reverse(uint8_t value) {
uint8_t result = 0;
for (std::size_t i = 0, j = 7; i < 8; ++i, --j) {
result |= ((value & (1 << j)) >> j) << i;
}
return result;
}
template<size_t... I>
constexpr auto make_lookup_table(std::index_sequence<I...>)
{
return std::array<uint8_t, sizeof...(I)>{reverse(I)...};
}
template<typename Indices = std::make_index_sequence<256>>
constexpr auto bit_reverse_lookup_table()
{
return make_lookup_table(Indices{});
}
constexpr auto lookup = bit_reverse_lookup_table();
int main(int argc)
{
return lookup[argc];
}
Upvotes: 0
Reputation: 1
unsigned char c ; // the original
unsigned char u = // the reversed
c>>7&0b00000001 |
c<<7&0b10000000 |
c>>5&0b00000010 |
c<<5&0b01000000 |
c>>3&0b00000100 |
c<<3&0b00100000 |
c>>1&0b00001000 |
c<<1&0b00010000 ;
Explanation: exchanged bits as per the arrows below.
01234567
<------>
#<---->#
##<-->##
###<>###
Upvotes: -1
Reputation: 803
I think this is simple enough
uint8_t reverse(uint8_t a)
{
unsigned w = ((a << 7) & 0x0880) | ((a << 5) & 0x0440) | ((a << 3) & 0x0220) | ((a << 1) & 0x0110);
return static_cast<uint8_t>(w | (w>>8));
}
or
uint8_t reverse(uint8_t a)
{
unsigned w = ((a & 0x11) << 7) | ((a & 0x22) << 5) | ((a & 0x44) << 3) | ((a & 0x88) << 1);
return static_cast<uint8_t>(w | (w>>8));
}
Upvotes: -1
Reputation: 229864
The simplest way is probably to iterate over the bit positions in a loop:
unsigned char reverse(unsigned char c) {
int shift;
unsigned char result = 0;
for (shift = 0; shift < CHAR_BIT; shift++) {
if (c & (0x01 << shift))
result |= (0x80 >> shift);
}
return result;
}
Upvotes: 10
Reputation: 103
This simple function uses a mask to test each bit in the input byte and transfer it into a shifting output:
char Reverse_Bits(char input)
{
char output = 0;
for (unsigned char mask = 1; mask > 0; mask <<= 1)
{
output <<= 1;
if (input & mask)
output |= 1;
}
return output;
}
Upvotes: 2
Reputation: 9
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i;
unsigned char rev = 0x70 ; // 0b01110000
unsigned char tmp = 0;
for(i=0;i<8;i++)
{
tmp |= ( ((rev & (1<<i))?1:0) << (7-i));
}
rev = tmp;
printf("%x", rev); //0b00001110 binary value of given number
return 0;
}
Upvotes: -1
Reputation: 29
typedef struct
{
uint8_t b0:1;
uint8_t b1:1;
uint8_t b2:1;
uint8_t b3:1;
uint8_t b4:1;
uint8_t b5:1;
uint8_t b6:1;
uint8_t b7:1;
} bits_t;
uint8_t reverse_bits(uint8_t src)
{
uint8_t dst = 0x0;
bits_t *src_bits = (bits_t *)&src;
bits_t *dst_bits = (bits_t *)&dst;
dst_bits->b0 = src_bits->b7;
dst_bits->b1 = src_bits->b6;
dst_bits->b2 = src_bits->b5;
dst_bits->b3 = src_bits->b4;
dst_bits->b4 = src_bits->b3;
dst_bits->b5 = src_bits->b2;
dst_bits->b6 = src_bits->b1;
dst_bits->b7 = src_bits->b0;
return dst;
}
Upvotes: 1
Reputation: 15
xor ax,ax
xor bx,bx
mov cx,8
mov al,original_byte!
cycle: shr al,1
jnc not_inc
inc bl
not_inc: test cx,cx
jz,end_cycle
shl bl,1
loop cycle
end_cycle:
reversed byte will be at bl register
Upvotes: -1
Reputation: 17507
template <typename T>
T reverse(T n, size_t b = sizeof(T) * CHAR_BIT)
{
assert(b <= std::numeric_limits<T>::digits);
T rv = 0;
for (size_t i = 0; i < b; ++i, n >>= 1) {
rv = (rv << 1) | (n & 0x01);
}
return rv;
}
EDIT:
Converted it to a template with the optional bitcount
Upvotes: 29
Reputation: 516
This one is based on the one BobStein-VisiBone provided
#define reverse_1byte(b) ( ((uint8_t)b & 0b00000001) ? 0b10000000 : 0 ) | \
( ((uint8_t)b & 0b00000010) ? 0b01000000 : 0 ) | \
( ((uint8_t)b & 0b00000100) ? 0b00100000 : 0 ) | \
( ((uint8_t)b & 0b00001000) ? 0b00010000 : 0 ) | \
( ((uint8_t)b & 0b00010000) ? 0b00001000 : 0 ) | \
( ((uint8_t)b & 0b00100000) ? 0b00000100 : 0 ) | \
( ((uint8_t)b & 0b01000000) ? 0b00000010 : 0 ) | \
( ((uint8_t)b & 0b10000000) ? 0b00000001 : 0 )
I really like this one a lot because the compiler automatically handle the work for you, thus require no further resources.
this can also be extended to 16-Bits...
#define reverse_2byte(b) ( ((uint16_t)b & 0b0000000000000001) ? 0b1000000000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000000010) ? 0b0100000000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000000100) ? 0b0010000000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000001000) ? 0b0001000000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000010000) ? 0b0000100000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000100000) ? 0b0000010000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000001000000) ? 0b0000001000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000010000000) ? 0b0000000100000000 : 0 ) | \
( ((uint16_t)b & 0b0000000100000000) ? 0b0000000010000000 : 0 ) | \
( ((uint16_t)b & 0b0000001000000000) ? 0b0000000001000000 : 0 ) | \
( ((uint16_t)b & 0b0000010000000000) ? 0b0000000000100000 : 0 ) | \
( ((uint16_t)b & 0b0000100000000000) ? 0b0000000000010000 : 0 ) | \
( ((uint16_t)b & 0b0001000000000000) ? 0b0000000000001000 : 0 ) | \
( ((uint16_t)b & 0b0010000000000000) ? 0b0000000000000100 : 0 ) | \
( ((uint16_t)b & 0b0100000000000000) ? 0b0000000000000010 : 0 ) | \
( ((uint16_t)b & 0b1000000000000000) ? 0b0000000000000001 : 0 )
Upvotes: 1
Reputation: 17
#define BITS_SIZE 8
int
reverseBits ( int a )
{
int rev = 0;
int i;
/* scans each bit of the input number*/
for ( i = 0; i < BITS_SIZE - 1; i++ )
{
/* checks if the bit is 1 */
if ( a & ( 1 << i ) )
{
/* shifts the bit 1, starting from the MSB to LSB
* to build the reverse number
*/
rev |= 1 << ( BITS_SIZE - 1 ) - i;
}
}
return rev;
}
Upvotes: -1
Reputation: 59347
I think a lookup table has to be one of the simplest methods. However, you don't need a full lookup table.
//Index 1==0b0001 => 0b1000
//Index 7==0b0111 => 0b1110
//etc
static unsigned char lookup[16] = {
0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, };
uint8_t reverse(uint8_t n) {
// Reverse the top and bottom nibble then swap them.
return (lookup[n&0b1111] << 4) | lookup[n>>4];
}
// Detailed breakdown of the math
// + lookup reverse of bottom nibble
// | + grab bottom nibble
// | | + move bottom result into top nibble
// | | | + combine the bottom and top results
// | | | | + lookup reverse of top nibble
// | | | | | + grab top nibble
// V V V V V V
// (lookup[n&0b1111] << 4) | lookup[n>>4]
This fairly simple to code and verify visually.
Ultimately this might even be faster than a full table. The bit arith is cheap and the table easily fits on a cache line.
Upvotes: 162
Related Questions
- reversing byte order in c
- How to reverse bits in a bitset?
- how to reverse the Bit operation in C
- How to reverse bits in only the most significant half of an integer and leave the other half (least significant bits) untouched?
- Reverse bits the obvious way
- Reversing the bits of an integer in C
- Reverse Bits Algorithm
- Reverse the order of bits in a bit array
- How to flip a specific bit in a byte in C?
- reverse a number's bits