How to reverse bits in a bitset?

Question

For example, I have the integer

a = 10;

and it's binary representation (for a 32 bit integer) is

00000000000000000000000000001010

and reversed, it becomes

01010000000000000000000000000000

Now I've seen this code, from this topcoder article that can accomplish this

x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);

Now is there some straightforward way to achieve the same effect. Perhaps by converting our bitset into a string, and then reversing that? The constructors and method for converting bitset to a string of a bitset are so complicated I can't seem to figure out how to do this.

Here's what I tried so far

#include <bitset>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <typeinfo>
#include <string>

using namespace std;

int main() {

    const unsigned int k = 32;


    int x = 10;
    bitset<k> nf(x);

    cout << nf << endl;

    string str =
        nf.to_string<char,string::traits_type,string::allocator_type>();

    reverse(str.begin(), str.end() + str.size());

    cout << str << endl;

    return 0;
}

But I'm getting this as the output:

00000000000000000000000000001010
G;ÿJG¥±žGsÿkìöUàä˜\éä˜\é

Yes, your proposed method (convert back and forth to/from a string) is correct, but you can directly reverse the bitset. Very straightforward. What's the problem you're facing? — user202729, Feb 01 '18 at 06:26
The proposed approach is pretty efficient. Converting via string will take some unnecessary looping and conversions - 1. convert decimal to binary. 2. binary to string conversion. 3. reverse the string. 4. string to binary conversion. 5. convert binary to decimal. — Saharsh, Feb 01 '18 at 06:27
I downvoted this because you made a simple typographical mistake - `str.end() + str.size()`. — user202729, Feb 01 '18 at 06:29
How would you reverse a normal array without `std::reverse`? (implement it yourself) Now do the same with `bitset`. It's similar to a `bool[]`. — user202729, Feb 01 '18 at 06:30
See [this](https://stackoverflow.com/questions/39820041/is-it-allowed-to-increment-an-end-iterator). (potential dupe) — user202729, Feb 01 '18 at 06:33
You can reverse the bitset the same way you would reverse a string (by doing 16 swaps; three assignments per swap), or even more straightforwardly by copying the bits to a new bitset in reverse order. It's ... straightforward. — Buster, Feb 01 '18 at 06:33
why is the bit twiddling way considered bad? It's pretty standard way to do it — Sopel, Mar 23 '20 at 00:58

score 12 · Accepted Answer · answered Feb 01 '18 at 07:09

12

This is the trivial inplace approach straight on a bitset:

template<std::size_t N>
void reverse(std::bitset<N> &b) {
    for(std::size_t i = 0; i < N/2; ++i) {
        bool t = b[i];
        b[i] = b[N-i-1];
        b[N-i-1] = t;
    }
}

answered Feb 01 '18 at 07:09

Matteo Italia

123,740
17
206
299

score 9 · Answer 2 · answered Feb 01 '18 at 06:58

Less code will win you some time in TopCoder SRMs. Following is what I would use in TopCoder SRMs (see it live here):

#include <algorithm>
#include <bitset>
#include <iostream>
#include <string>

int main() {
  auto x = std::bitset<32>(10);
  std::cout << x << std::endl;

  auto str = x.to_string();
  std::reverse(str.begin(), str.end());
  auto y = std::bitset<32>(str);
  std::cout << y << std::endl;

  return 0;
}

score 2 · Answer 3 · edited Oct 25 '19 at 14:53

2

Without using any standard library functions (aside from printing the result):

#include<iostream>
#include<bitset>

const int size = sizeof(int)*CHAR_BIT;

int main()
{
    int x = 10;
    int r = 0;
    for(int i = 0; i < size; i++)
    {
        r = r << 1 | (x & 1);
        x >>= 1;
    }
    std::bitset<size> bits(r);
    std::cout << "Reverse " << bits << std::endl;

}

edited Oct 25 '19 at 14:53

Matteo Italia

123,740
17
206
299

answered Feb 01 '18 at 07:05

Mats Petersson

126,704
14
140
227

score 0 · Answer 4 · answered Feb 01 '18 at 06:46

0

Please check this one method :)

#include <iostream>
#include <bitset>

template<std::size_t N>
std::bitset<N> reverse(const std::bitset<N> &bit_set) {
  std::bitset<N> reversed;
  for (int i = 0, j = N - 1; i < N; i++, j--) {
    reversed[j] = bit_set[i];
  }
  return reversed;
}

int main() {
  std::bitset<32> b1(10);
  std::bitset<32> reversed_b1 = reverse(b1);
  std::cout << b1;
  std::cout << "\nand reversed\n" << reversed_b1 << std::endl;
  return 0;
}

answered Feb 01 '18 at 06:46

BartekPL

2,290
1
17
34

Maybe `sizeof(int)*CHAR_BIT` instead of `32` for cross-platform? Why not reverse directly on the bitset? – xskxzr Feb 01 '18 at 06:56
If you worked directly on the input bitset you would have to swap() the 2 members, and do half the calls. – Gem Taylor Feb 01 '18 at 17:54

score 0 · Answer 5 · answered Jul 04 '21 at 22:42

0

uint32_t reverseBits(uint32_t n) {
    bitset<32> b(n);                       // store in binary form 
    string s=b.to_string();               //put it in string
    string k(s.rbegin(),s.rend());       //reverse string
    bitset<32>d(k);                      //again put new string k  in bitset
    return  d.to_ulong();               //get value in decimal form
    
    
}

answered Jul 04 '21 at 22:42

Deepesh arya

7
2

Wow, it's nearly as inefficient as can be. You don't have to allocate two string on the heap in order to reverse a `uint32_t`. – firegurafiku Dec 09 '22 at 19:06

score 0 · Answer 6 · answered Aug 07 '23 at 04:41

You can use __builtin_bitreverse family of utilities offered by the clang compiler.

https://clang.llvm.org/docs/LanguageExtensions.html#builtin-bitreverse

int x = 10;
std::bitset<sizeof(int)*8> nf(x); // 00000000000000000000000000001010
std::bitset<sizeof(int)*8> nf_reverse(__builtin_bitreverse32(x)); // 01010000000000000000000000000000

How to reverse bits in a bitset?

6 Answers6