Rotasi Kanan Bit di C
Saya mengerjakan latihan 2-8 di K&R yang meminta kita untuk menulis fungsi rightrot(int x, int n)
sehingga semua bit x
bergeser 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 94
karena 122
adalah 1111010
dan 94
adalah 1011110
. Sebaliknya, saya mendapatkan 30
yang 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
Mari kita analisis (~0 ^ (~0 >> 1) )
:
~0
adalah -1
~0 >> 1
lagi -1
, jika sedikit tanda adalah 1
rightshift akan mengisi bit baru dengan 1
s.
-1 ^ -1
adalah 0
.
x = x | 0
adalah 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 x
juga harus unsigned int
.
https://ideone.com/7zPTQk