( ((byte & 0x1) << 7) | ((byte & 0x2) << 5) | ((byte & 0x4) << 3) | \
((byte & 0x8) << 1) | ((byte & 0x10) >> 1 ) | ((byte & 0x20) >> 3) | \
((byte & 0x40) >> 5) | ((byte & 0x80) >> 7) )

외에 특별한 방법이 있을까요? 음;

IEEE 에서 bit reverse로 journal 검색해보세요.

선지자들의 알고리즘이 많이 있습니다. pseudo code까지 포함해서 말이지요.

const unsigned char BIT8[8] = {0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80};

const unsigned char BIT8REV[8] = {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};

unsinged char ReverseByte(unsigned char byte)
{
unsigned char byte_rev=0x00;

for(i=0;i<8;i++)
{
if(byte&BIT8[i]) byte_rev |= BITREV[i]
}

return byte_rev;
}
/* 여기까지 */

이렇게 하면 되지 않을까요? ^^;

testing

256 크기의 배열을 만드시고 인덱스와 원하는 거꾸로의 값으로 채운 다음 필요할 때 그 배열을 참조하시면 바로 답이 나오지 않을까요?

한번 만들어 보았습니다.

#include <stdio.h>

inline unsigned char left_rotate( unsigned char x, int l )
{
        return ((x<<l) & 0xff) | ((x>>(8-l)) & 0xff);
}

int main()
{
        unsigned char x,y;
        x = 0x54; /* expected: 0x2a */
        printf("%x\n", x );
        y = left_rotate( x,4 );
        x = (x & 0xcc) | (y & 0x33);
        y = left_rotate( x,1 );
        x = left_rotate( y,2 );
        y = (x & 0xaa) | (y & 0x55 );
        printf("%x\n", y );
        return 0;
}

좀 난해하죠?

ANSI C++ 표준 라이브러리의 bitset 클래스와 reverse 알고리듬을 사용하면 간단하게 구현할 수 있습니다. (5분에 완성... ^^)

//---------------------------------------------------------------------------
#include <iostream>
#include <string>
#pragma hdrstop
#include <bitset>
#include <algorithm>
//---------------------------------------------------------------------------

// unsigned char 뿐만 아니라, unsigned short와 unsigned int에도 적용 가능한 템플릿 함수입니다.
template <typename T>
T reverse_bits(T n)
{
    using namespace std;

    typedef bitset<sizeof(T) * 8> bitset_t;
    bitset_t b(n);
    string s = b.to_string<char, char_traits<char>, allocator<char> >();
    reverse(s.begin(), s.end());

    return bitset_t(s).to_ulong();
}

int main()
{
    using namespace std;

    typedef bitset<sizeof(unsigned char) * 8> bitset8;

    unsigned char n = 0x54, r = 0;

    cout.setf(ios::hex, ios::basefield);
    cout.setf(ios::showbase);
    cout << "n == " << hex << static_cast<int>(n) << " == " << bitset8(n) << endl;
    cout << "Reversing all bits of m to r ...\n";
    r = reverse_bits(n);
    cout << "r == " << hex << static_cast<int>(r) << " == " << bitset8(r) << endl;

    return 0;
}
//---------------------------------------------------------------------------

실행 결과:

n == 0x54 == 01010100
Reversing all bits of m to r ...
r == 0x2a == 00101010

가상적으로 87654321을 놓고 생각하면 편합니다.
bit도 아니고.. 암튼 자리수 채우는 물건입니다.

        x =  87654321
        y = left_rotate( x,4 );         // y = 43218765
        x = (x & 0xcc) | (y & 0x33);  // x = 87214365
        y = left_rotate( x,1 );        // y = 72143658
        x = left_rotate( y,2 );        // x= 14365872
                                        // 오라 x의 홀수번째는 1,3,5,7 y의 짝수번째는 2,4,6,8
        y = (x & 0xaa) | (y & 0x55 );    // 그것들만 가져와서 or하니 12345678!!

 

typedef bitset<numeric_limits<unsigned char>::digts> bitset_t;

가 더 좋겠습니다.

좋은 지적 감사합니다. 수정해서 다시 올립니다.

//---------------------------------------------------------------------------
#include <iostream>
#include <limits>
#include <string>
#pragma hdrstop
#include <bitset>
#include <algorithm>
//---------------------------------------------------------------------------

template <typename T>
T reverse_bits(T n)
{
    using namespace std;

    typedef bitset<numeric_limits<T>::digits> bitset_t;
    bitset_t b(n);
    string s = b.to_string<char, char_traits<char>, allocator<char> >();
    reverse(s.begin(), s.end());

    return bitset_t(s).to_ulong();
}

int main()
{
    using namespace std;

    typedef bitset<numeric_limits<unsigned char>::digits> bitset_uc;

    unsigned char n = 0x54, r = 0;

    cout.setf(ios::hex, ios::basefield);
    cout.setf(ios::showbase);
    cout << "n == " << hex << static_cast<int>(n) << " == " << bitset_uc(n) << endl;
    cout << "Reversing all bits of m to r ...\n";
    r = reverse_bits(n);
    cout << "r == " << hex << static_cast<int>(r) << " == " << bitset_uc(r) << endl;

	return 0;
}
//---------------------------------------------------------------------------

yui 님께서 잘 설명해주셔서 더 설명할 것이 없군요.
rotate, shift, bit 연산이 어셈블리어일때 적당한 알고리즘입니다만,
sodomau 님이 하신것과 성능상 얼마나 좋은지는 모르겠습니다.

일단 가독성은 너무 떨어지고, 그렇다고 연산이 그렇게 작은 것 같지는 않거든요.

htonl 함수같은 구현을 물어 볼때 알고있는 알고리즘이라서 bit 수준에서도 적용해볼까해서 만들어 본 것입니다.

좋은 프로그램 감사합니다.
근데 전 에러가 나네요. 이게 뭔 조화인지...

제가 지금 g++를 테스트할 수가 없습니다. 죄송....
제가 최초로 올린 소스는 Borland C++Builder 6으로 컴파일 했고요,
MS Visual C++.NET 2003(7.1)에서 컴파일할 때는
#include <limits>
를 추가해야만 컴파일됩니다.
코드 수정해 놓았습니다.

헤더파일간의 포함 관계는 표준에 정의되어 있지 않기 때문에, 컴파일러에 따라 이런 차이가 생깁니다.

그리고 #pragma hdrstop은 precompiled header에서 제외하는 헤더 파일을 지정하는 것으로, 주로 윈도용 컴파일러에서 사용합니다.
주로, 사용자 정의 헤더 파일이나, 템플릿 라이브러리 헤더파일 앞에 지정하지요.
대응하는 gcc의 #pragma는 잘 모르겠네요. 위 메시지처럼 잘못 지정해도 warning만 날 뿐, 컴파일은 이상없습니다.

b.template to_string 으로 고치면 됩니다...

bugiii 님 방법 한표!! 8)

이런 문법이 있었군요.
그럼 표준에서는 g++의 방식만 인정하는 건가요?
BC++과 VC++의 문법은 표준에 위배되는 건가요?

흠 제가 지금 맥을 쓰고 있어서 vc 7.1에서는
테스트 할 수 없군요..

.tempalte 혹은 ->template construct가 고안된 이유가 위의 예제와 같은 문맥에서 컴파일러가 '<' 이 문자가 less then인지 아님 template의 시작을 의미하는 문자인지 알 수 있는 방법이 없기 때문임을 생각한다면 vc7.1이 저 코드를 에러없이 컴파일 했다는게 좀 의심스럽군요.

bc++는 표준에 매우 위배되는게 많고 vc는 7.1이 나오면서 template partial specialization 및 기타 6.0의 많은 문제를 해결했다고는 아직 template쪽의 표준을 완전하게는 구현하지 못한것 같습니다. (C++ Templates의 more CRTP 예제를 컴파일 못하더군요) 뭐 gcc도 마찬가지이긴 하지만...

여하튼 reverse_bits 이 함수 여러모로 공부 많이 되서 좋습니다. ^^;

논란의 여지가 있지만,
제가 위의 답변을 보고 느낀껀, bugiii 님의 답을 제외하고는
일종의 기술적 유희만을 너무 염두에 두신 것 같습니다

문제가 1바이트에 대한 비트의 조작(8비트 라고 합시다)이라고 정의를
한 것 치고는, 너무 장황한 답변만이 올라오는군요.

옛말에도 하나의 문제에 대해 하나의 간단한 답, 하나의 복잡한 답이 있으면,
간단한 것이 진리라고 햇습니다.

저는 bugiii님의 말씀대로 lookup table이 가장 타당한 답이 아닌가 생각되는데요.

비트의 변환을 위해서 왜 굳이 비트 연산이 필요한가요?

이 간단한 문제에 c++에다 namespace에 template이라니!!! 맙소사..

#include <iostream>
#include <bitset>

using namespace std;

int main()
{
bitset<8> num1 = 10;
bitset<8> num2 = 0xff;
string outPut;

num1 ^= num2;

outPut = num1.to_string();
cout << outPut.c_str() << endl;

return 0;
}

가장 간단한 것이 항상 진리는 아닙니다.
여기서는 단지 8비트만 뒤집는 경우이지만, 16, 32, 64비트라면 어떨까요.
비트가 늘어남에 따라 룩업 테이블의 크기는 기하급수적으로 늘어나 버립니다.
임베디드 시스템에서는 아예 구현이 불가능하죠. i8051이나 AVR 같은 8비트 시스템에서는 256바이트 배열을 여러번 쓰는 것도 꽤 부담스러운 일입니다. 그래서 위와 같은 복잡한 비트 연산이 필요할 경우도 있는 겁니다.

std::bitset은 ANSI C++의 표준 라이브러리에 포함되어 있는 기능입니다.
어떤 언어에서든지 표준 라이브러리는 언어의 일부로서, 그 언어를 사용하는 프로그래머에게는 공통적인 어휘 역할을 하는 것입니다.
콘솔 출력을 하기 위해, C에서는 printf, C++에서는 cout <<, Java에서는 System.out.println을 쓰는 것처럼, C++에서의 비트 조작에 bitset을 쓰는 건 너무나 자연스러운 겁니다.
C++ 언어의 특징 때문에 bitset::to_string() 함수를 쓰는 것이 좀 귀찮아서 어렵게 보였을 뿐, 제가 쓴 코드는 상당히 간단한 겁니다.

1. bitset의 내용을 string으로 옮긴다.
2. reverse 알고리듬을 적용한다.
3. 변환된 string을 다시 bitset으로 변환한다.

CPU 사양이 정 안되면 니블 단위로 끊어서 16 바이트크기의 테이블을 구성해서 몇번 반복하면 됩니다. 8 비트 CPU 아니라, 프로그래머블 시퀀서일지라도 할건 해야죠.

게다가 초소형 임베디드 시스템에서는 설령 C/C++ 을 쓰더라도 C 라이브러리까지 쓸수있는 경우는 드뭅니다.

문제의 스펙이 1바이트에 대한 조작이 전부가 아니죠. for루프도 쓰지 않고 멋도 있었으면 좋겠다는 것입니다. (끝가지 읽어보면) for루프 이야기가 나온거 보면 thisrule님도 lookup table 생각해보셨을 겁니다.

아웅... 너무 심각하게 받아들이지 않으셨으면 합니다. 그냥 이런 저런 방법으로 구현할 수 있겠구나 하고 넘어가시면 좋겠습니다. 그냥 재미삼아 여러가지 구현이 나올 수도 있구요. 그런 와중에 좋은 방법이 나올 수도 있지 않을까요?

하다못해 CPU 종속적인 비트 역전 어셈블리 명령어도 하나의 답글이 될 수도 있습니다. (아예 비트를 역순으로 바꿔주는 명령어가 존재하는 CPU도 있습니다. 8, 16, 32비트 다 되는 걸로 기억합니다.)

특정 비트 유무의 검사를 마스크 배열을 이용해서 해결하거나 이런식의 비트 변경은 임베디드에서 흔히 쓰이는 기법이라 아무 생각없이 말씀드린거니까요. 그럴 수도 있구나 해주시면 좋겠습니다. 하드웨어에서도 어드레스 디코딩 회로를 논리회로로 하지 않고 일반 롬 테이블을 이용해서 무식하게 하는 방법도 있습니다. (물론 배보다 배꼽이 더 큰 경우가 많지만요)

저도 잘못한 것이 그 배열에 어떻게 정확하게 변환값을 집어 넣는가는 빠트린 것입니다. 그런 것을 다른 분들이 올려주신 알고리즘으로 해결하시면 될 것이구요.

중요한 것은 정확한 변환 값을 얻는 것이 먼저라고 생각합니다. 그 후에 좀 더 빠른 변환 알고리즘이나 테이블에 채워서 사용해야 한다고 생각합니다.

역시나 비난의 글이 쏟아지는군요..

조목조목 비판하시는 모습을 보니, 왠지 서글프네요.

본의를 알아 주셨으면 좋겠습니다.

저도 거의 십여년간 이 바닥에서 구르고 있는 사람입니다.

답변을 다신 분들의 의도를 몰라서 그런게 아닙니다.

over-engineering이라는 화두가 생각이 나서 올린 글입니다.

건승하시길.

김성진 드림

이방법이 가장보편적으로 생각할수 있는방법인것 같은데..

Bit reverse 오퍼레이션을 데이터에도 적용할수 있는 CPU 도 있나요? 보통 DSP 에서는 FFT 할때 쓰라고 어드레싱 레지스터에 bit reverse 옵션을 줄수있는 경우가 대부분이었던것 같은 기억이 가물가물한데요... FFT 말고는 별로 쓸데가 없었던것으로 기억도 나구요.

typedif struct
{
	unsigned int b1 : 1;
	unsigned int b2 : 1;
	unsigned int b3 : 1;
	unsigned int b4 : 1;
	unsigned int b5 : 1;
	unsigned int b6 : 1;
	unsigned int b7 : 1;
	unsigned int b8 : 1;
} RBIT;

RBIT bits, rbits;

rbits.b1 = bits.b8;
rbits.b2 = bits.b7;
rbits.b3 = bits.b6;
rbits.b4 = bits.b5;
rbits.b5 = bits.b4;
rbits.b6 = bits.b3;
rbits.b7 = bits.b2;
rbits.b8 = bits.b1;

제가 발의한 내용이 명예의 전당에 올라간 줄도 모르고 있었군요.(부끄 :oops: )
물론 모두가 답글을 다신 분들의 힘이지요.
아뭏든 이렇게 많은 방법과 알고리듬이 있는줄 몰랐습니다.
또, C++에 대하여 더 깊이 공부해야겠다는 생각도 듭니다.

혹시 C/C++ 말고 python이나 perl로 하면 더 멋진 코드가 나올까요?

인라인 어셈블러로 rol 이나 ror을 쓰는게 가장 간단할 것 같군요.

TI의 240x 시리즈 제품은 어드레스 모드중 비트 반전 어드레스를 지원 합니다.
다른 시리즈는 안 다뤄 봐서 보르겠네요.

table driven :!:
가장 빠르고, 비용도 저렴한 방법으로 보입니다. :wink:

ruby 버전입니다.

class Integer
  def bitrev(zfill=8)
    ("%0#{zfill}b" % self).reverse.to_i(2)
  end
end

puts "%064b" % (-2**32)
puts "%064b" % (2**32-1)
puts "%064b" % (-2**32).bitrev(64)
puts "%064b" % (2**32-1).bitrev(64)

멋진 방법이죠. 예전에 sin에서 쓴 것을 보고 충격먹었던 적이 기억납니다. :-)

[덧붙임: 원래 발제와는 좀 의도가 벗어난 것같군요 :-) ]

이건 메모릴 너무 먹겠군요. 4비트에 대해 16개의 테이블로 바꿔치기 하는걸 두번 반복하는게 낫겠습니다.

typedif 를 typedef 로 바꿔야 하지 않나요?

바이트일경우..

                x = (x >> 4) | (x << 4);
                x = (x >> 2 & 0x33) | (x << 2 & 0xcc);
                x = (x >> 1 & 0x55) | (x << 1 & 0xaa);

이렇게 쓰는군요..

새로운거 종종 배우게 되는군요..

비트 반전이면

C나 C++경우 ~ 연산자 하나면 끝나는데.....

제가 문제를 잘 못 파악한건지..
뒤늦은 댓글이지만

이 책에 비트 다루는 신기한 공식이 많이 포함되어 있습니다.
비트와 바이트를 뒤집기라는 장이 따로 있을 정도입니다.

x라는 8비트 정수를 뒤집기 위해서는 (절반을 중심으로 반대 위치로 옮기는것)

s = (x* 0x00020202) & 0x01044010
t = (x* 0x00080808) & 0x02088020
결과 = mod(s+t,4095)

이렇게 하면 된다고 하네요 이해는 안되지만 신기하지 않습니까 ^^;
이책을 사놓고 볼 시간이 없어서 안보고 있었는데 이렇게 쓸모가 있네요

재밌는 글입니다. ^^

CPU 마다 다르겠지만, 제일 간단한 Shift Right 명령과 Underflow 플래그를 사용해서 8 번의 논리연산을 통해 답이 나오게 하는 경우도 있고, 곱셈기 성능이 좋으면 곱셈기를 이용하여, 정수 나눗셈을 위한 LUT가 있으면 나눗셈을 이용한 방법도 쓸 수 있고요... 최상의 성능을 내는 요인은 CPU 내의 ALU 회로와 그것을 고려한 컴파일러가 얼마나 훌륭한 결과물을 뽑아내느냐에 따라 다르겠지요. ^^

여러가지 알고리즘으로 구현을 하는 이유도 각 아키텍쳐마다, 혹은 수행해야 하는 목적 프로세스마다 다르게 적용하기 위해서입니다.

공학에서는 성능과 관계없이 가장 적합한 것을 얻는 것이 답이니까요. :)
====
( - -)a 이제는 학생으로 가장한 백수가 아닌 진짜 백수가 되어야겠다.

변수 하나의 값을 뒤집는 상황이 아니라, unsigned char *array 형의 배열의 원소 전체의 값을 뒤집는 상황에 대해서 조사해 보았습니다. 일반적으로 reverse 함수를 배열의 원소의 수만큼 반복해서 호출해 주어야겠죠. 32비트 CPU인 경우, 이걸 어떻게 좀 효율적으로 처리할 수 없을까 조사하는 중에 재미있는 사실을 알아냈습니다.

unsigned int reverse_8x4( unsigned int c )
{
    c = ((c & 0x55555555) << 1) | ((c >> 1) & 0x55555555);
    c = ((c & 0x33333333) << 2) | ((c >> 2) & 0x33333333);
    c = ((c & 0x0f0f0f0f) << 4) | ((c >> 4) & 0x0f0f0f0f);

    return c;
}

함수를 호출할 때, 캐스팅을 사용해서 배열요소 4개를 함꺼번에 32bit 정수형으로 해서 넘겨주게 되면, 각각 8비트 단위로 비트가 뒤집히게 됩니다. 다른 배열요소들을 건드리지 않습니다. 이 알고리즘이 가지는 또다른 장점이겠군요. :-)

unsigned char reverse( unsigned char c ); 형으로 함수를 설계하고 0x55, 0x33 등을 쓰는 것보다 많이 효율적으로 사용할 수 있을 거라 생각합니다.

16비트 배열의 각각의 요소를 뒤집을 경우에는

unsigned int reverse_16x2( unsigned int c )
{
    c = ((c & 0x55555555) << 1) | ((c >> 1) & 0x55555555);
    c = ((c & 0x33333333) << 2) | ((c >> 2) & 0x33333333);
    c = ((c & 0x0f0f0f0f) << 4) | ((c >> 4) & 0x0f0f0f0f);
    c = ((c & 0x00ff00ff) << 8) | ((c >> 8) & 0x00ff00ff);

    return c;
}

/***********************************
웃자! 몸만 건강하면 뭘 못해먹고 살겠냐!
************************************/

테이블을 이용하면 좀 멋있으려나?

int main()
{
char bitRevTable[16] = {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};

char a = 0x35; // 예제..
char b;

b = (bitRevTable[(a >> 4)&0x0f]) | (bitRevTable[a & 0x0f] << 4);

...

return 0;
}

테이블을 이용하면 좀 멋있으려나?

int main()
{
char bitRevTable[16] = {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};

char a = 0x35; // 예제..
char b;

b = (bitRevTable[(a >> 4)&0x0f]) | (bitRevTable[a & 0x0f] << 4);

...

return 0;
}

테이블을 이용하면 좀 멋있으려나?

int main()
{
char bitRevTable[16] = {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};

char a = 0x35; // 예제..
char b;

b = (bitRevTable[(a >> 4)&0x0f]) | (bitRevTable[a & 0x0f] << 4);

...

return 0;
}

너무 단순하게 해결했나? 위의 분들은 화려한 초식이 난무한데..흠좀무

BYTE inverse(BYTE s)
{
   return
     ((s & 0x80) >> 7 |
      (s & 0x40) >> 5 |
      (s & 0x20) >> 3 |
      (s & 0x10) >> 1 |
      (s & 0x08) << 1 |
      (s & 0x04) << 3 |
      (s & 0x02) << 5 |
      (s & 0x01) << 7);
}

Small is beautiful..

최적화를 위한 최적의 소스 코드!!

아름다움을 추구하는건 간단함이 살아 있어야 한다가..

제 생각입니다..

재밌네요

댓글달기.ㅋ.ㅋ

이런 저런 방식이 많이 나와 있군요..

제가 선호하는 건 굉장히 성능에 critical 한 경우가 아니라면
초보자도 이해가 쉽도록 하는 게 좋다.... 는 ..

잘 배웠습니다 ^^

잘 배웠습니다. 아.. 근데 글 저장할 수 있는 다른 방법은 없나요..

1.1+2+3+6=2.
2.=ㄱ
12비트를 1비트로는 못 만들어도 ㄱ으로 치환 할수 있죠
자연로그(ln)이용 하시면 더 빠르고요~~!!
-------------------------------------------
식탁은 언제든지 열려 있다 와서 먹으세요~!

http://nametag.naver.com/04449cOadeMKdcAU