رازها

رازها

تمرین یادگیری

مقدمه

ارقام دودویی در نهایت مستقیماً به ترانزیستورهای پردازنده یا حافظه‌ی شما نگاشت می‌شوند و به اینکه هر کدام «روشن» است یا «خاموش».

دستکاری در سطح پایین، که به‌طور غیررسمی «بازی با بیت‌ها» نامیده می‌شود، در زبان‌های سیستمی اهمیت ویژه‌ای دارد.

زبان‌های سطح بالا مثل Julia معمولاً بیشتر این جزئیات را پنهان می‌کنند. با این حال، مجموعه‌ی کاملی از عملیات سطح بیت در خود زبان پایه در دسترس است.

نکته: برای دیدن خروجی دودویی خوانا برای انسان در محیط تعاملی REPL، تقریباً همه‌ی مثال‌های زیر باید درون یک تابع bitstring() قرار بگیرند. این کار از نظر بصری حواس‌پرت‌کن است، بنابراین بیشتر جاهایی که این تابع ظاهر شده حذف شده‌اند.

عملیات جابه‌جایی بیت

انواع عدد صحیح، علامت‌دار یا بدون علامت، را می‌توان به‌صورت رشته‌ای از ۱ و ۰ نمایش داد.

julia> bitstring(UInt8(5))
"00000101"

جابه‌جایی بیت فقط همه‌چیز را به‌اندازه‌ی تعداد مشخصی موقعیت به چپ یا راست منتقل می‌کند. در انواع UInt، چند بیت از یک سر بیرون می‌ریزند و سر دیگر با صفر پر می‌شود:

julia> ux::UInt8 = 5
5

julia> bitstring(ux)
"00000101"

julia> ux << 2 # left by 2
"00010100"

julia> ux >> 1 # right by 1
"00000010"

هر جابه‌جایی به چپ مقدار را دو برابر می‌کند و هر جابه‌جایی به راست آن را نصف می‌کند (البته با در نظر گرفتن بریده شدن). این موضوع در نمایش ده‌دهی واضح‌تر است:

julia> 3 << 2
12

julia> 24 >> 3
3

این نوع جابه‌جایی بیت بسیار سریع‌تر از حساب «رسمی» است و همین باعث شده این تکنیک در کدنویسی سطح پایین بسیار رایج شود.

با اعداد صحیح علامت‌دار، باید کمی محتاط‌تر باشیم.

جابه‌جایی به چپ نسبتاً ساده است:

julia> sx = Int8(5)
5

julia> sx # positive integer
"00000101"

julia> sx << 2
"00010100"

julia> -sx # negative integer
"11111011"

julia> -sx << 2
"11101100"

بنابراین جابه‌جایی به چپ برای اعداد صحیح علامت‌دار مثبت همانند اعداد صحیح بدون علامت است.

مقادیر منفی به شکل مکمل دو ذخیره می‌شوند، یعنی چپ‌ترین بیت ۱ است. برای جابه‌جایی به چپ مشکلی نیست، اما هنگام جابه‌جایی به راست چپ‌ترین بیت‌ها را چگونه پر می‌کنیم؟

julia> sx >> 2 # simple for positive values!
"00000001"

julia> -sx # negative integer
"11111011"

julia> -sx >> 2 # pad with repeated sign bit
"11111110"

julia> -sx >>> 2 # pad with 0
"00111110"

عملگر >> جابه‌جایی حسابی را انجام می‌دهد و بیت علامت را حفظ می‌کند.

عملگر >>> جابه‌جایی منطقی را انجام می‌دهد و با صفر پر می‌کند، انگار که عدد بدون علامت است.

منطق بیتی

در یکی از مفاهیم پیشین دیدیم که عملگرهای && (و)، || (یا) و ! (نقیض) با مقادیر منطقی به کار می‌روند.

عملگرهای معادلی هم وجود دارند: & (و بیتی)، | (یا بیتی) و ~ (یک تیلدا، نقیض بیتی) که بیت‌های دو عدد صحیح را مقایسه می‌کنند.

julia> 0b1011 & 0b0010 # bit is 1 in both numbers
"00000010"

julia> 0b1011 | 0b0010 # bit is 1 in at least one number
"00001011"

julia> ~0b1011 # flip all bits
"11110100"

julia> xor(0b1011, 0b0010) # bit is 1 in exactly one number, not both
"00001001"

در اینجا، xor() همان «یا انحصاری» است که به‌صورت تابع به کار می‌رود.

دستورالعمل‌ها

دوستتان همین حالا پیامی برایتان فرستاده است که رازی مهم در آن است. او نمی‌خواست خواندن آن برای دیگران آسان باشد، پس پیام را با انجام مجموعه‌ای از دستکاری‌های بیتی رمزنگاری کرده است. برای کمک به رمزگشایی پیام، باید توابعی بنویسید.

1. شیفت دادن بیت‌ها به عقب

نخستین گام در رمزگشایی پیام این است که شیفت انجام‌شده در فرایند رمزنگاری را با شیفت دادن بیت‌ها به سمت راست خنثی کنید. در ادامه‌ی فرایند رمزگشایی گام‌های دیگری هم هست که فرض می‌کند صفرها از سمت چپ وارد می‌شوند.

تابع shift_back() را پیاده‌سازی کنید که یک مقدار و تعداد جای شیفت را می‌گیرد و شیفت را انجام می‌دهد.

shift_back(0b1001, 2) # => 0b0010

2. تنظیم چند بیت

در گام بعد، چند بیت هست که باید روی ۱ تنظیم شوند.

تابع set_bits() را پیاده‌سازی کنید که یک مقدار و یک ماسک می‌گیرد و نتیجه‌ی تنظیم بیت‌های مقدار روی ۱ را برمی‌گرداند. هر بیتی از value که بیت متناظر در mask هم ۱ باشد، باید روی ۱ تنظیم شود. بقیه‌ی بیت‌ها باید بدون تغییر بمانند.

set_bits(0b0110, 0b0101) # => 0b0111

3. وارونه کردن بیت‌های مشخص

برخی بیت‌ها هنگام رمزنگاری وارونه می‌شوند. برای رمزگشایی پیام باید این بیت‌ها دوباره وارونه شوند.

تابع flip_bits() را پیاده‌سازی کنید که یک مقدار و یک ماسک می‌گیرد. ماسک مشخص می‌کند کدام بیت‌های مقدار باید وارونه شوند. اگر بیتی در mask برابر ۱ باشد، آن بیت در value وارونه می‌شود. بقیه‌ی بیت‌ها بدون تغییر می‌مانند.

flip_bits(0b1100, 0b0101) # => 0b1001

4. صفر کردن بیت‌های مشخص

و در آخر، بیت‌های مشخصی هم هستند که همیشه به ۰ رمزگشایی می‌شوند.

تابع clear_bits() را پیاده‌سازی کنید که یک مقدار و یک ماسک می‌گیرد. هر بیتی در value که بیت متناظر در ماسک برابر ۱ باشد، باید روی ۰ تنظیم شود. بقیه‌ی بیت‌ها باید بدون تغییر بمانند.

clear_bits(0b0110, 0b0101) # => 0b0010
ویرایش از طریق GitHub این لینک در پنجره یا زبانه‌ی جدیدی باز می‌شود
Julia Exercism

آماده‌اید رازها را شروع کنید؟

در Exercism ثبت‌نام کنید تا Julia را همراه با 35 مفهوم128 تمرین و مربی‌گری انسانی واقعی یاد بگیرید و در آن استاد شوید، همه‌ی این‌ها رایگان.