Praktik terbaik untuk operasi pergeseran melingkar (rotate) di C ++

96

Operator shift kiri dan kanan (<< dan >>) sudah tersedia di C ++. Namun, saya tidak dapat menemukan bagaimana saya dapat melakukan operasi rotasi atau shift melingkar.

Bagaimana operasi seperti "Putar Kiri" dan "Putar Kanan" dilakukan?

Berputar ke kanan dua kali di sini 

Initial --> 1000 0011 0100 0010

harus menghasilkan:

Final   --> 1010 0000 1101 0000

Sebuah contoh akan sangat membantu.

(catatan editor: Banyak cara umum untuk mengekspresikan rotasi di C mengalami perilaku tidak terdefinisi jika jumlah rotasi nol, atau dikompilasi ke lebih dari satu instruksi mesin rotasi tunggal. Jawaban pertanyaan ini harus mendokumentasikan praktik terbaik.)

c++ c rotation bit-manipulation c++-faq Elroy
sumber
Kemungkinan duplikat Rotasi waktu hampir konstan yang tidak melanggar standar
jww
1
Ini telah tiba di C ++ 20! stackoverflow.com/a/57285854/895245
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Jawaban:

106

Lihat juga versi sebelumnya dari jawaban ini pada pertanyaan rotasi lainnya dengan beberapa detail lebih lanjut tentang apa yang diproduksi asm gcc / clang untuk x86.

Cara paling ramah kompiler untuk mengekspresikan rotate dalam C dan C ++ yang menghindari Perilaku Tidak Terdefinisi tampaknya adalah implementasi John Regehr . Saya telah menyesuaikannya untuk memutar dengan lebar tipe (menggunakan tipe lebar tetap seperti uint32_t).

#include <stdint.h>   // for uint32_t
#include <limits.h>   // for CHAR_BIT
// #define NDEBUG
#include <assert.h>

static inline uint32_t rotl32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);  // assumes width is a power of 2.

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n<<c) | (n>>( (-c)&mask ));
}

static inline uint32_t rotr32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n>>c) | (n<<( (-c)&mask ));
}

Berfungsi untuk semua jenis bilangan bulat unsigned, tidak hanya uint32_t, jadi Anda dapat membuat versi untuk ukuran lain.

Lihat juga versi template C ++ 11 dengan banyak pemeriksaan keamanan (termasuk static_assertbahwa lebar tipe adalah pangkat 2) , yang tidak terjadi pada beberapa DSP 24-bit atau mainframe 36-bit, misalnya.

Saya akan merekomendasikan hanya menggunakan template sebagai back-end untuk pembungkus dengan nama yang menyertakan lebar putar secara eksplisit. Aturan promosi integer berarti bahwa rotl_template(u16 & 0x11UL, 7)akan melakukan rotasi 32 atau 64-bit, bukan 16 (bergantung pada lebarnya unsigned long). Even uint16_t & uint16_tdipromosikan signed intoleh aturan integer-promotion C ++, kecuali pada platform intyang tidak lebih luas dari uint16_t.

Pada x86 , versi ini sejajar dengan saturol r32, cl (atau rol r32, imm8) dengan kompiler yang melakukannya, karena kompilator tahu bahwa instruksi rotate dan shift x86 menutupi jumlah shift dengan cara yang sama seperti yang dilakukan sumber C.

Dukungan kompiler untuk idiom penghindaran UB ini pada x86, untuk uint32_t xdan unsigned int nuntuk perubahan jumlah variabel:

  • dentang: dikenali untuk putaran hitung variabel sejak dentang3.5, beberapa shift + atau insns sebelum itu.
  • gcc: dikenali untuk putaran hitung variabel sejak gcc4.9 , beberapa shift + atau insns sebelumnya. gcc5 dan yang lebih baru juga mengoptimalkan cabang dan mask di versi wikipedia, hanya dengan menggunakan instruksi roratau roluntuk jumlah variabel.
  • icc: didukung untuk putaran hitung variabel sejak ICC13 atau sebelumnya . Penggunaan rotasi hitungan konstan shld edi,edi,7yang lebih lambat dan membutuhkan lebih banyak byte daripada rol edi,7pada beberapa CPU (terutama AMD, tetapi juga beberapa Intel), ketika BMI2 tidak tersedia untuk rorx eax,edi,25menyimpan MOV.
  • MSVC: x86-64 CL19: Hanya dikenali untuk putaran hitungan konstan. (Idiom wikipedia dikenali, tetapi cabang dan AND tidak dioptimalkan). Gunakan _rotl/ _rotrintrinsics dari <intrin.h>pada x86 (termasuk x86-64).

gcc untuk ARM menggunakan and r1, r1, #31untuk berputar variabel-hitung, tapi masih melakukan rotate yang sebenarnya dengan instruksi tunggal : ror r0, r0, r1. Jadi gcc tidak menyadari bahwa jumlah rotasi pada dasarnya bersifat modular. Seperti yang dikatakan dokumen ARM, “ROR dengan panjang shift n,, lebih dari 32 sama dengan ROR dengan panjang shift n-32” . Saya pikir gcc menjadi bingung di sini karena pergeseran kiri / kanan pada ARM memenuhi hitungan, jadi pergeseran sebesar 32 atau lebih akan menghapus register. (Tidak seperti x86, di mana shift mask hitungannya sama dengan rotates). Ia mungkin memutuskan bahwa ia membutuhkan instruksi AND sebelum mengenali idiom rotate, karena cara kerja non-circular shift pada target tersebut.

Kompiler x86 saat ini masih menggunakan instruksi tambahan untuk menutupi jumlah variabel untuk putaran 8 dan 16-bit, mungkin karena alasan yang sama mereka tidak menghindari AND pada ARM. Ini adalah pengoptimalan yang terlewat, karena performa tidak bergantung pada jumlah rotasi pada CPU x86-64 mana pun. (Penyembunyian hitungan diperkenalkan dengan 286 untuk alasan kinerja karena menangani pergeseran secara berulang, bukan dengan latensi konstan seperti CPU modern.)

BTW, lebih memilih rotate-right untuk variabel-count rotates, untuk menghindari compiler yang 32-nmenerapkan rotasi kiri pada arsitektur seperti ARM dan MIPS yang hanya menyediakan rotate-right. (Ini mengoptimalkan dengan penghitungan konstanta waktu kompilasi.)

Fun Fakta: ARM tidak benar-benar memiliki dedicated pergeseran / petunjuk rotate, itu hanya MOV dengan sumber operan melalui laras-shifter dalam modus ROR : mov r0, r0, ror r1. Jadi rotate bisa dilipat menjadi operand sumber register untuk instruksi EOR atau sesuatu.

Pastikan Anda menggunakan tipe unsigned untuk ndan nilai kembaliannya, jika tidak maka tidak akan berputar . (gcc untuk target x86 melakukan pergeseran kanan aritmatika, menggeser salinan bit-tanda daripada nol, yang mengarah ke masalah ketika Anda ORmenggeser dua nilai bersama-sama. Pergeseran kanan bilangan bulat bertanda negatif adalah perilaku yang ditentukan implementasi di C.)

Juga, pastikan hitungan shift adalah tipe unsigned , karena (-n)&31dengan tipe yang ditandatangani bisa menjadi pelengkap atau tanda / besaran, dan tidak sama dengan 2 ^ n modular yang Anda dapatkan dengan komplemen unsigned atau two. (Lihat komentar di posting blog Regehr). unsigned intbekerja dengan baik pada setiap kompiler yang saya lihat, untuk setiap lebarnya x. Beberapa tipe lain benar-benar mengalahkan pengenalan idiom untuk beberapa kompiler, jadi jangan hanya menggunakan tipe yang sama seperti x.

Beberapa kompiler menyediakan intrinsik untuk rotasi , yang jauh lebih baik daripada inline-asm jika versi portabel tidak menghasilkan kode yang baik pada kompilator yang Anda targetkan. Tidak ada intrinsik lintas platform untuk kompiler apa pun yang saya ketahui. Ini adalah beberapa opsi x86:

  • Dokumen Intel yang <immintrin.h>menyediakan _rotldan _rotl64intrinsik , dan sama untuk shift kanan. MSVC membutuhkan <intrin.h>, sedangkan gcc membutuhkan <x86intrin.h>. An #ifdefmenangani gcc vs. icc, tetapi clang tampaknya tidak menyediakannya di mana pun, kecuali dalam mode kompatibilitas MSVC dengan-fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . Dan asm yang dipancarkannya menyebalkan (masking ekstra dan CMOV).
  • MSVC: _rotr8dan_rotr16 .
  • gcc dan icc (bukan clang): <x86intrin.h>juga menyediakan __rolb/ __rorbuntuk putar 8-bit kiri / kanan, __rolw/ __rorw(16-bit), __rold/ __rord(32-bit), __rolq/ __rorq(64-bit, hanya ditentukan untuk target 64-bit). Untuk rotasi sempit, implementasi menggunakan __builtin_ia32_rolhiatau ...qi, tetapi rotasi 32 dan 64-bit ditentukan menggunakan shift / atau (tanpa perlindungan terhadap UB, karena kode di ia32intrin.hhanya harus bekerja di gcc untuk x86). GNU C tampaknya tidak memiliki __builtin_rotatefungsi lintas platform seperti yang dilakukannya __builtin_popcount(yang berkembang menjadi apa pun yang optimal pada platform target, meskipun itu bukan satu instruksi). Sebagian besar waktu Anda mendapatkan kode yang bagus dari pengenalan idiom.

// For real use, probably use a rotate intrinsic for MSVC, or this idiom for other compilers.  This pattern of #ifdefs may be helpful
#if defined(__x86_64__) || defined(__i386__)

#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>  // Not just <immintrin.h> for compilers other than icc
#endif

uint32_t rotl32_x86_intrinsic(rotwidth_t x, unsigned n) {
  //return __builtin_ia32_rorhi(x, 7);  // 16-bit rotate, GNU C
  return _rotl(x, n);  // gcc, icc, msvc.  Intel-defined.
  //return __rold(x, n);  // gcc, icc.
  // can't find anything for clang
}
#endif

Agaknya beberapa kompiler non-x86 memiliki intrinsik juga, tapi jangan memperluas jawaban wiki-komunitas ini untuk memasukkan semuanya. (Mungkin lakukan itu dalam jawaban yang ada tentang intrinsik ).

(Versi lama dari jawaban ini menyarankan asm sebaris khusus MSVC (yang hanya berfungsi untuk kode 32bit x86), atau http://www.devx.com/tips/Tip/14043 untuk versi C. Komentar tersebut membalasnya .)

Asm sebaris mengalahkan banyak pengoptimalan , terutama gaya MSVC karena memaksa masukan untuk disimpan / dimuat ulang . Sebuah GNU C inline-asm rotate yang ditulis dengan hati-hati akan memungkinkan penghitungan menjadi operan langsung untuk penghitungan shift konstan waktu kompilasi, tetapi masih tidak dapat mengoptimalkan sepenuhnya jika nilai yang akan digeser juga merupakan konstanta waktu kompilasi setelah sebaris. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Peter Cordes
sumber
1
Penasaran, mengapa tidak bits = CHAR_BIT * sizeof(n);dan c &= bits - 1;dan return ((n >> c) | (n << (bits - c))), mana yang akan saya gunakan?
mirabilos
@mirabilos: Versi Anda memiliki UB dengan bits = 32, count = 32, di geser dengan bits - c= 32 - 0. (Saya tidak mendapatkan ping dari ini karena saya hanya mengedit wiki, bukan menulisnya di tempat pertama.)
Peter Cordes
@PeterCordes 0 < count < bitsadalah persyaratan konstan dari hampir semua CPU dan bahasa pemrograman yang mengimplementasikan rotasi (terkadang 0 ≤ count < bits, tetapi menggeser dengan jumlah bit yang tepat hampir selalu tidak ditentukan atau dibulatkan ke nop alih-alih menghapus nilainya, dan berputar, yah.)
mirabilos
@mirabilos: Benar, tetapi tujuan kami adalah menulis fungsi yang memasukkan hitungan shift secara langsung ke instruksi asm tunggal, tetapi menghindari UB pada level C untuk hitungan shift yang memungkinkan. Karena C tidak memiliki operator atau fungsi putar, kami ingin menghindari UB di salah satu bagian komponen idiom ini. Kami lebih suka tidak bergantung pada kompilator yang memperlakukan shift C dengan cara yang sama seperti instruksi shift asm pada target kompilasi nya. (Dan BTW, ARM melakukan nol register dengan pergeseran jumlah variabel lebih dari lebar register, mengambil hitungan dari byte bawah register. Tautan di jawabannya.)
Peter Cordes
1
Saya akan mengatakan "cukup gunakan cuplikan portabel" tetapi kemudian saya memeriksa kodenya dan tampaknya (a) memanggil UB untuk jumlah shift nol dan (b) hanya menggunakan intrinsik pada MSVC . Secara umum meskipun menjadikannya sebagai "kode referensi" yang dapat dikompilasi untuk apa yang berfungsi dengan semua peretasan khusus kompiler dan platform sepertinya ide yang bagus ...
BeeOnRope
33

Karena ini C ++, gunakan fungsi inline:

template <typename INT> 
INT rol(INT val) {
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

Varian C ++ 11:

template <typename INT> 
constexpr INT rol(INT val) {
    static_assert(std::is_unsigned<INT>::value,
                  "Rotate Left only makes sense for unsigned types");
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}
MSalters
sumber
5
Peringatan: Kode ini rusak jika INTmerupakan bilangan bulat bertanda dan tanda disetel! Ujian misalnya rol<std::int32_t>(1 << 31)yang harus dibalik ke 1 tetapi benar-benar menjadi -1(karena tandanya dipertahankan).
Tidak ada yang pindah dari SE
9
@Nobody: Saya sudah berkomentar 5 tahun yang lalu bahwa Anda tidak boleh menggunakan tipe integer bertanda tangan. Rotasi tidak masuk akal pada jenis integer yang ditandatangani.
MSalters
2
Anda dapat menggunakan std::numeric_limits<INT>::digitssebagai pengganti CHAR_BIT * sizeof. Saya lupa jika tipe unsigned diperbolehkan memiliki padding yang tidak digunakan (misalnya integer 24-bit disimpan dalam 32 bit), tetapi jika demikian maka digitsakan lebih baik. Lihat juga gist.github.com/pabigot/7550454 untuk versi dengan pemeriksaan lebih lanjut untuk perubahan jumlah variabel.
Peter Cordes
1
@PeterCordes: Benar. Saya pikir Cray melakukannya (menggunakan register floating point dengan padding di mana bidang eksponen berada).
MSalters
2
@ fake-name '> jadi versi C ++ 11 tidak akan berfungsi di windows kecuali jika Anda mengubahnya ke yang lain ...' Ya, ubah itu ke linux. :)
Slava
21

Kebanyakan kompiler memiliki intrinsik untuk itu. Visual Studio misalnya _rotr8, _rotr16

VolkerK
sumber
Wow! jauh lebih mudah daripada jawaban yang diterima. btw, untuk DWORD (32-bit) gunakan _rotr dan _rotl.
Gabe Halsmer
16

C ++ 20 std::rotldanstd::rotr

Itu telah datang! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html dan harus menambahkannya ke <bit>tajuk.

cppreference mengatakan bahwa penggunaannya akan seperti:

#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t i = 0b00011101;
    std::cout << "i          = " << std::bitset<8>(i) << '\n';
    std::cout << "rotl(i,0)  = " << std::bitset<8>(std::rotl(i,0)) << '\n';
    std::cout << "rotl(i,1)  = " << std::bitset<8>(std::rotl(i,1)) << '\n';
    std::cout << "rotl(i,4)  = " << std::bitset<8>(std::rotl(i,4)) << '\n';
    std::cout << "rotl(i,9)  = " << std::bitset<8>(std::rotl(i,9)) << '\n';
    std::cout << "rotl(i,-1) = " << std::bitset<8>(std::rotl(i,-1)) << '\n';
}

memberikan keluaran:

i          = 00011101
rotl(i,0)  = 00011101
rotl(i,1)  = 00111010
rotl(i,4)  = 11010001
rotl(i,9)  = 00111010
rotl(i,-1) = 10001110

Saya akan mencobanya ketika dukungan datang ke GCC, GCC 9.1.0 g++-9 -std=c++2amasih belum mendukungnya.

Proposal tersebut mengatakan:

Header: 

namespace std {
  // 25.5.5, rotating   
  template<class T>
    [[nodiscard]] constexpr T rotl(T x, int s) noexcept;
  template<class T>
    [[nodiscard]] constexpr T rotr(T x, int s) noexcept;

dan:

25.5.5 Memutar [bitops.rot]

Dalam deskripsi berikut, misalkan N menunjukkan std::numeric_limits<T>::digits.

template<class T>
  [[nodiscard]] constexpr T rotl(T x, int s) noexcept;

Batasan: T adalah tipe integer unsigned (3.9.1 [basic.fundamental]).

Misalkan r menjadi s% N.

Pengembalian: Jika r adalah 0, x; jika r positif (x << r) | (x >> (N - r)),; jika r negatif rotr(x, -r),.

template<class T>
  [[nodiscard]] constexpr T rotr(T x, int s) noexcept;

Batasan: T adalah tipe integer unsigned (3.9.1 [basic.fundamental]). Misalkan r menjadi s% N.

Pengembalian: Jika r adalah 0, x; jika r positif (x >> r) | (x << (N - r)),; jika r negatif rotl(x, -r),.

A std::popcountjuga ditambahkan untuk menghitung jumlah 1 bit: Bagaimana menghitung jumlah bit set dalam integer 32-bit?

Ciro Santilli 新疆 改造 中心 法轮功 六四 事件
sumber
Kenapa rotasi bit butuh waktu lama untuk mendarat di c ++ modern? Bahkan di LLVM clang, hanya ada intrinsik beberapa tahun yang lalu => reviews.llvm.org/D21457 Saya pikir ARM telah berputar jauh sebelum 2010, jadi mereka seharusnya sudah ada sejak c ++ 11.
Sandthorn
15

Pasti:

template<class T>
T ror(T x, unsigned int moves)
{
  return (x >> moves) | (x << sizeof(T)*8 - moves);
}
Dídac Pérez
sumber
6
Apakah itu 8salah eja CHAR_BIT(yang tidak harus persis 8)?
Toby Speight
2
Karena ini adalah jawaban yang sama dengan saya (kecuali menukar dari kanan ke kiri), komentar Peter Cordes pada jawaban saya juga berlaku di sini: gunakan std::numeric_limits<T>::digits.
MSalters
7

Bagaimana dengan sesuatu seperti ini, menggunakan bitset standar ...

#include <bitset> 
#include <iostream> 

template <std::size_t N> 
inline void 
rotate(std::bitset<N>& b, unsigned m) 
{ 
   b = b << m | b >> (N-m); 
} 

int main() 
{ 
   std::bitset<8> b(15); 
   std::cout << b << '\n'; 
   rotate(b, 2); 
   std::cout << b << '\n'; 

   return 0;
}

HTH,

Abhay
sumber
Perlu memodifikasinya untuk memperhitungkan pergeseran yang lebih besar dari panjang bitet.
H. Green
Ditambahkan m %= N;ke akun untuk shift >= N.
Milania
7

Jika x adalah nilai 8 bit, Anda dapat menggunakan ini:

x=(x>>1 | x<<7);
Farhadix
sumber
2
Mungkin akan berperilaku buruk jika xditandatangani.
sam hocevar
6

Secara rinci, Anda dapat menerapkan logika berikut.

Jika Pola Bit 33602 di Integer

1000 0011 0100 0010

dan Anda perlu Roll over dengan 2 shif kanan kemudian: pertama buat salinan pola bit dan kemudian geser ke kiri: Panjang - RightShift yaitu panjang 16 nilai pergeseran kanan adalah 2 16 - 2 = 14

Setelah 14 kali pergeseran kiri Anda dapatkan.

1000 0000 0000 0000

Sekarang geser nilai ke kanan 33602, 2 kali sesuai kebutuhan. Anda mendapatkan

0010 0000 1101 0000

Sekarang ambil nilai OR antara 14 kali nilai pergeseran kiri dan 2 kali nilai pergeseran kanan.

1000 0000 0000 0000
0010 0000 1101 0000
===================
1010 0000 1101 0000
===================

Dan Anda mendapatkan nilai rollover yang bergeser. Ingat operasi yang sedikit bijak lebih cepat dan ini bahkan tidak memerlukan loop apa pun.

SM Kamran
sumber
1
Mirip dengan subrutin di atas ... b = b << m | b >> (Nm);
SM Kamran
Bukankah seharusnya itu XOR, bukan OR? 1 ^ 0 = 1, 0 ^ 0 = 0, dll. Jika ATAU tidak eksklusif, maka akan selalu 1.
BK
5

Dengan asumsi Anda ingin menggeser ke kanan demi Lbit, dan inputnya xadalah angka dengan Nbit:

unsigned ror(unsigned x, int L, int N) 
{
    unsigned lsbs = x & ((1 << L) - 1);
    return (x >> L) | (lsbs << (N-L));
}
nimrodm
sumber
4

Jawaban yang benar adalah sebagai berikut:

#define BitsCount( val ) ( sizeof( val ) * CHAR_BIT )
#define Shift( val, steps ) ( steps % BitsCount( val ) )
#define ROL( val, steps ) ( ( val << Shift( val, steps ) ) | ( val >> ( BitsCount( val ) - Shift( val, steps ) ) ) )
#define ROR( val, steps ) ( ( val >> Shift( val, steps ) ) | ( val << ( BitsCount( val ) - Shift( val, steps ) ) ) )
pengguna3102555
sumber
Mungkin akan berperilaku buruk jika valditandatangani.
sam hocevar
0

Kode Sumber x nomor bit

int x =8;
data =15; //input
unsigned char tmp;
for(int i =0;i<x;i++)
{
printf("Data & 1    %d\n",data&1);
printf("Data Shifted value %d\n",data>>1^(data&1)<<(x-1));
tmp = data>>1|(data&1)<<(x-1);
data = tmp;  
}
kjk
sumber
0

saran lain

template<class T>
inline T rotl(T x, unsigned char moves){
    unsigned char temp;
    __asm{
        mov temp, CL
        mov CL, moves
        rol x, CL
        mov CL, temp
    };
    return x;
}
SalemD
sumber
0

Di bawah ini adalah versi jawaban Dídac Pérez yang sedikit lebih baik , dengan kedua arah diterapkan, bersama dengan demo penggunaan fungsi ini menggunakan unsigned char dan unsigned long long values. Beberapa catatan:

  1. Fungsi-fungsi tersebut dibuat sebaris untuk pengoptimalan compiler
  2. Saya menggunakan cout << +valuetrik untuk mengeluarkan karakter unsigned secara singkat yang saya temukan di sini: https://stackoverflow.com/a/28414758/1599699
  3. Saya merekomendasikan penggunaan <put the type here>sintaks eksplisit untuk kejelasan dan keamanan.
  4. Saya menggunakan unsigned char untuk parameter shiftNum karena apa yang saya temukan di bagian Detail Tambahan di sini :

Hasil dari operasi shift tidak terdefinisi jika ekspresi aditif negatif atau jika ekspresi aditif lebih besar dari atau sama dengan jumlah bit dalam ekspresi shift (dipromosikan) .

Ini kode yang saya gunakan:

#include <iostream>

using namespace std;

template <typename T>
inline T rotateAndCarryLeft(T rotateMe, unsigned char shiftNum)
{
    static const unsigned char TBitCount = sizeof(T) * 8U;

    return (rotateMe << shiftNum) | (rotateMe >> (TBitCount - shiftNum));
}

template <typename T>
inline T rotateAndCarryRight(T rotateMe, unsigned char shiftNum)
{
    static const unsigned char TBitCount = sizeof(T) * 8U;

    return (rotateMe >> shiftNum) | (rotateMe << (TBitCount - shiftNum));
}

void main()
{
    //00010100 == (unsigned char)20U
    //00000101 == (unsigned char)5U == rotateAndCarryLeft(20U, 6U)
    //01010000 == (unsigned char)80U == rotateAndCarryRight(20U, 6U)

    cout << "unsigned char " << 20U << " rotated left by 6 bits == " << +rotateAndCarryLeft<unsigned char>(20U, 6U) << "\n";
    cout << "unsigned char " << 20U << " rotated right by 6 bits == " << +rotateAndCarryRight<unsigned char>(20U, 6U) << "\n";

    cout << "\n";


    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
    {
        cout << "unsigned char " << 21U << " rotated left by " << +shiftNum << " bit(s) == " << +rotateAndCarryLeft<unsigned char>(21U, shiftNum) << "\n";
    }

    cout << "\n";

    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
    {
        cout << "unsigned char " << 21U << " rotated right by " << +shiftNum << " bit(s) == " << +rotateAndCarryRight<unsigned char>(21U, shiftNum) << "\n";
    }


    cout << "\n";

    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
    {
        cout << "unsigned long long " << 3457347ULL << " rotated left by " << +shiftNum << " bit(s) == " << rotateAndCarryLeft<unsigned long long>(3457347ULL, shiftNum) << "\n";
    }

    cout << "\n";

    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
    {
        cout << "unsigned long long " << 3457347ULL << " rotated right by " << +shiftNum << " bit(s) == " << rotateAndCarryRight<unsigned long long>(3457347ULL, shiftNum) << "\n";
    }

    cout << "\n\n";
    system("pause");
}
Andrew
sumber
0 
--- Substituting RLC in 8051 C for speed --- Rotate left carry
Here is an example using RLC to update a serial 8 bit DAC msb first:
                               (r=DACVAL, P1.4= SDO, P1.5= SCLK)
MOV     A, r
?1:
MOV     B, #8
RLC     A
MOV     P1.4, C
CLR     P1.5
SETB    P1.5
DJNZ    B, ?1

Here is the code in 8051 C at its fastest:
sbit ACC_7  = ACC ^ 7 ; //define this at the top to access bit 7 of ACC
ACC     =   r;
B       =   8;  
do  {
P1_4    =   ACC_7;  // this assembles into mov c, acc.7  mov P1.4, c 
ACC     <<= 1;
P1_5    =   0;
P1_5    =   1;
B       --  ; 
    } while ( B!=0 );
The keil compiler will use DJNZ when a loop is written this way.
I am cheating here by using registers ACC and B in c code.
If you cannot cheat then substitute with:
P1_4    =   ( r & 128 ) ? 1 : 0 ;
r     <<=   1;
This only takes a few extra instructions.
Also, changing B for a local var char n is the same.
Keil does rotate ACC left by ADD A, ACC which is the same as multiply 2.
It only takes one extra opcode i think.
Keeping code entirely in C keeps things simpler sometimes.
MikeZ
sumber
-1

Kelebihan fungsi:

unsigned int rotate_right(unsigned int x)
{
 return (x>>1 | (x&1?0x80000000:0))
}

unsigned short rotate_right(unsigned short x) { /* etc. */ }
graham.reeds
sumber
-1 
#define ROTATE_RIGHT(x) ( (x>>1) | (x&1?0x8000:0) )
Dan Byström
sumber
Anda harus membungkus x ke dalam tanda kurung untuk menghindari kejutan yang tidak menyenangkan dengan ekspresi sebagai argumen untuk makro.
Joey
3
Jika nilainya bukan 16-bit, Anda diam-diam mendapatkan omong kosong
James Hopkin
Jika mendefinisikannya sebagai makro, seseorang juga harus berhati-hati untuk menghindari melewatkan ekspresi dengan efek samping sebagai argumen.
Phil Miller