مراقبه های LeetCode: تعداد 1 بیت

Summarize this content to 400 words in Persian Lang
بیایید با توضیحات این مورد شروع کنیم:

با یک عدد صحیح مثبت n، تابعی بنویسید که تعداد بیت های مجموعه را در نمایش باینری آن (همچنین به عنوان وزن همینگ نیز شناخته می شود) برمی گرداند.

به عنوان مثال:

Input: n = 11
Output: 3

Explanation: The input binary string 1011 has a total of three set bits.

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

یا:

Input: n = 128
Output: 1

Explanation: The input binary string 10000000 has a total of one set bit.

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

یا:

Input: n = 2147483645
Output: 30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

همانطور که در مقدمه فصل در پست قبل اشاره کردیم، الف بیت را تنظیم کنید به بیتی با مقدار 1 اشاره دارد.

بنابراین، کاری که باید انجام دهیم این است که 1 بیت را بشماریم.

یک راه برای انجام این کار این است که عدد را به رشته تبدیل کنید و فقط 1 ها را بشمارید. یا، می توانیم آن را به یک آرایه تبدیل کنیم و 0 ها را فیلتر کرده و طول آن را بدست آوریم. اما، رویکرد دیگری وجود دارد که می توانیم از دستکاری بیت استفاده کنیم.

می‌توانیم بیت‌های مجموعه (بیت‌هایی که مقدار 1 دارند) را حذف کنیم تا عدد 0 شود.

یک چیز خوب برای دانستن این است که n – 1 است سمت راست ترین نسخه حذف شده از n.

به عنوان مثال، اگر n 00 است10، n – 1 00 است01.

یا اگر n 01 است10، n – 1 01 است01.

توجه داشته باشید

مهم نیست که n – 1 دیگری را معرفی می کند 1s زیرا ما در حال انجام عملیات AND برای شمارش بیت های مجموعه هستیم. به عنوان مثال، اگر n است 0000، سپس n – 1 است 0111. و آنها خواهند بود 0000. یا اگر n است 0010، سپس n – 1 است 0001. سمت راست ترین بیت n است 0 در n – 1، و این تمام چیزی است که اهمیت دارد.

ما می توانیم یک حلقه ایجاد کنیم که تا زمانی که 1 بیت در آن وجود دارد اجرا شود n، هر کدام را که می رویم بشماریم.همچنین هر بار، ما می توانیم یک و عملیات با n و 1 کمتر از آن (n & (n – 1)).

یک راه حل ساده TypeScript به شکل زیر است:

function hammingWeight(n: number): number {
let result = 0;
while (n > 0) {
n &= (n – 1);
result++;
}

return result;
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

پیچیدگی زمان و مکان

به نظر من پیچیدگی زمانی این است

O(لog n)O(log\n) O(لog n)

– در بدترین حالت وقتی همه بیت‌ها تنظیم شده‌اند، از حلقه عبور می‌کنیم

لog nlog \ n لog n

بار (تعداد بیت ها در نمایش باینری یک عدد

nn n

خواهد بود

لog nlog \ n لog n

).

پیچیدگی فضا ثابت خواهد بود (

O(1)O (1) O(1)

) زیرا با افزایش ورودی، استفاده از حافظه اضافی وجود ندارد.

مشکل بعدی که به آن خواهیم پرداخت Counting Bits است. تا آن زمان، کد نویسی مبارک.

Input: n = 11
Output: 3

Explanation: The input binary string 1011 has a total of three set bits.

Input: n = 128
Output: 1

Explanation: The input binary string 10000000 has a total of one set bit.

Input: n = 2147483645
Output: 30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

function hammingWeight(n: number): number {
  let result = 0;
  while (n > 0) {
    n &= (n - 1);
    result++;
  }

  return result;
}