Rotasi Kanan Bit di C

Jan 03 2021

Saya mengerjakan latihan 2-8 di K&R yang meminta kita untuk menulis fungsi rightrot(int x, int n)sehingga semua bit xbergeser n kali ke kanan dengan bit yang jatuh dari ujung kanan muncul kembali di ujung kiri.

Inilah solusi yang saya coba di mana saya menggeser setiap bit satu per satu:

int rightrot(int x, int n)
{
    int i, rmb;

    for(i = 0; i < n; ++i)
    {
        // get right-most bit
        rmb = x & 1;

        // shift 1 to right
        x = x >> 1;

        // if right-most bit is set, set left-most bit
        if (rmb == 1)
            x = x | (~0 ^ (~0 >> 1) );
    }

    return x;
}

Ketika saya jalankan rightrot(122, 2), saya berharap untuk mendapatkan 94karena 122adalah 1111010dan 94adalah 1011110. Sebaliknya, saya mendapatkan 30yang kebetulan 0011110. Jelas, metode saya untuk menyetel bit paling kiri tidak berfungsi seperti yang saya harapkan. Apakah ada yang melihat kesalahan yang jelas? Saya baru belajar tentang menangkap bit dan sejenisnya.

CATATAN: Saya mendapatkan teknik untuk mengatur bit paling kiri dari posting ini.

Jawaban

7 mch Jan 02 2021 at 23:21

Mari kita analisis (~0 ^ (~0 >> 1) ):

~0adalah -1
~0 >> 1lagi -1, jika sedikit tanda adalah 1rightshift akan mengisi bit baru dengan 1s.
-1 ^ -1adalah 0.
x = x | 0adalah x.

Solusinya adalah Anda harus menggunakan tipe data yang tidak bertanda tangan jika Anda ingin melakukan operasi bit.

Jadi Anda harus menggunakan baris x = x | (~0u ^ (~0u >> 1) );
Untuk menghindari masalah lain parameter xjuga harus unsigned int.

https://ideone.com/7zPTQk