نمایش نسخه قابل چاپ
سلام به همه دوستان گرامی
چند روزی هست که درگیری مباحث بیتی شدم و البته دارم به بهترین روش و البته اپتیمایز ترین روش عمل میکنم چرا که تعداد سیکل ماشین صرف شده مهم هست و باید سیستم بالاترین سرعت رو داشته باشه
طرح مساله
یک آرایه 256 درایه ای از نوع متغییر لانگ داریم به این صورت
که این متغییر جایی جایی پر میشه و مساله از این به بعد شروع میشهکد:long a[256];
حالا میخوام تعداد بیت های 1 این آرایه رو به دست بیارم که این ارایه ما 1024 بیت داره
حالا بهترین روش برای بدست آوردن تعداد یک ها چی هست
کسی نیست که بخواد چیزی بگه و نظری داشته باشه
هر عنصر شما 4 بایت یعنی 32 بیت هست و 257 عنصر شما 1028 بایت هست نه بیت!
میتونی با استفاده از یه ارایه دیگه ایندکس عنصرهایی که یک شدن رو بدست بیاری...
من هم خواستم حرف بهنام رو بنویسم که ایشون نوشتند.
پس الان یک کم روی سوال مبهم شد! تعداد بیت هایی که در کل عناصر این آرایه یک هستن رو می خوای ببینی چیه یا تعداد عناصر این آرایه که مقدارشون یک هستن؟
لطفا اون روش اولیه که به ذهن خودتون هم رسیده بذارید شاید همون رو بشه بهتر پرورش داد تا از اول یه ایده جدید داد.
من که فکر نمیکنم روش خاصی داشته باشه !
اینم نظر من برا 1 بایت :
[PHP]
for (int i=0;i<32;i++){
Nbit+=Byte%2;
byte=byte/2;
}
[/PHP]
حق با شماست ولی کلیت ماجرا هیچ فرقی نمیکنه حالا با این حساب 8 کیلو بیت داریم که میخوایم ببینیم چند تا از این بیت ها یک هست؟نقل قول:
هر عنصر شما 4 بایت یعنی 32 بیت هست و 257 عنصر شما 1028 بایت هست نه بیت!
میتونی با استفاده از یه ارایه دیگه ایندکس عنصرهایی که یک شدن رو بدست بیاری...
و در مورد نظر آقای [Dear Guest/Member you can't see link before replyclick here to register] هم باید بگم که روششون کار میکنه ولی به درد ما نمیخوره این روش خیلی کند هست انجام محاسبه تقسیم و باقی مانده
روش سریعتر
متغیر شما حتمن باید 256 عنصری باشه؟
و اینکه گفتی جای جایی پر میشه یعنی به ترتیب ایندکس پر نمیشه درسته؟
میتونید تغییر بدید اندازه رو
در مورد ایندکس هم باید بگم که نه به ترتیب ایندکس پر نمی شه
روش and بیتی با عدد یک که هی شیفت داده میشه چطور؟نقل قول:
فکر کنم دنبال راه حلی هستید که روی تک تک بیت ها یک بار پردازش مجزا نکنیم. درسته؟
خب چرا اون لحظه ای که تو ارایه میخوای بنویسی، بیتهای مقدار جدید رو نمیشماری؟
اینطوری نیازی نیست که مثلن توی یه حلقه یا هرچیزی بخوای کل بیتهای ارایه رو بشماری!
اون کار رو نمیشه کرد که موقه نوشتن بیت ها رو چک کنیم چرا که سرعت خیلی مهم هست
بله حق با آقای ، آقایی فر هست نمیخوام برای هر بیت شرطی قائل باشم
البته به راهکار رسیدم و الان بیشتر جنبه هوش آزمایی داره:0013:
با سلام
امکان دارد هیچ یک از بیتهای مثلا عنصر ارایه شماره 1 اصلا یک نباشد پس چک کردن بیتهای آن وقت تلف کردن است پس اول کل بیتها را چک میکنیماگر بزگتر از صفر بود میتوانیم 16 بیت پایین ویا بالاکد:if(arr[1]>0)
وکد:int aa=0xffff & arr[1]
و حتی 8 بیت بالا و پایین به این ترتیب با کوچک کردن منطقه جستجو زمان را خیلی کوچک میکنیمکد:if(aa>0)
خوب میبینم که دوستان دارن هی به جواب نزدیک تر میشن !
آقای [Dear Guest/Member you can't see link before replyclick here to register] راه کار خوبی هست ولی کافی نیست - من در ابتدا از این روش استفاده کرده بودم ولی باز سرعت کافی نداره !
راه حلی که من پیاده کردم تعداد 90112 بیت رو با فرایند خوندن از SPI و چک کردن بیت های اون الان 90 میلی ثانیه طول میکشه با سرعت 40 مگا هرتزی که 80 میلی ثانیه صرف خوندن از SPI میشه :wink:
منتظر راهکار بهتر شما هستم
آقای مزارعی راه حلت رو رو کن دیگه!
احتمالا دنبال همچین چیزی هستی. تست هم کردمش خودم:
[PHP]
int NumberOfSetBits(int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
[/PHP]
تعدادی از الگوریتم های این کار در لینک زیر از دانشگاه استنفورد موجوده
[Dear Guest/Member you can't see link before replyclick here to register]