PDA

توجه ! این یک نسخه آرشیو شده میباشد و در این حالت شما عکسی را مشاهده نمیکنید برای مشاهده کامل متن و عکسها بر روی لینک مقابل کلیک کنید : محاسبات بیتی ساده !



agape
28-10-2012, 13:12
سلام به همه دوستان گرامی
چند روزی هست که درگیری مباحث بیتی شدم و البته دارم به بهترین روش و البته اپتیمایز ترین روش عمل میکنم چرا که تعداد سیکل ماشین صرف شده مهم هست و باید سیستم بالاترین سرعت رو داشته باشه
طرح مساله
یک آرایه 256 درایه ای از نوع متغییر لانگ داریم به این صورت

long a[256];
که این متغییر جایی جایی پر میشه و مساله از این به بعد شروع میشه
حالا میخوام تعداد بیت های 1 این آرایه رو به دست بیارم که این ارایه ما 1024 بیت داره
حالا بهترین روش برای بدست آوردن تعداد یک ها چی هست

agape
28-10-2012, 19:12
کسی نیست که بخواد چیزی بگه و نظری داشته باشه

behnam6500
28-10-2012, 20:31
هر عنصر شما 4 بایت یعنی 32 بیت هست و 257 عنصر شما 1028 بایت هست نه بیت!

میتونی با استفاده از یه ارایه دیگه ایندکس عنصرهایی که یک شدن رو بدست بیاری...

Aghaeifar
28-10-2012, 21:06
من هم خواستم حرف بهنام رو بنویسم که ایشون نوشتند.
پس الان یک کم روی سوال مبهم شد! تعداد بیت هایی که در کل عناصر این آرایه یک هستن رو می خوای ببینی چیه یا تعداد عناصر این آرایه که مقدارشون یک هستن؟

لطفا اون روش اولیه که به ذهن خودتون هم رسیده بذارید شاید همون رو بشه بهتر پرورش داد تا از اول یه ایده جدید داد.

M_GH
28-10-2012, 23:10
من که فکر نمیکنم روش خاصی داشته باشه !

اینم نظر من برا 1 بایت :


for (int i=0;i<32;i++){
Nbit+=Byte%2;
byte=byte/2;
}

agape
28-10-2012, 23:22
هر عنصر شما 4 بایت یعنی 32 بیت هست و 257 عنصر شما 1028 بایت هست نه بیت!

میتونی با استفاده از یه ارایه دیگه ایندکس عنصرهایی که یک شدن رو بدست بیاری...
حق با شماست ولی کلیت ماجرا هیچ فرقی نمیکنه حالا با این حساب 8 کیلو بیت داریم که میخوایم ببینیم چند تا از این بیت ها یک هست؟

و در مورد نظر آقای M_GH (You can see links before reply) هم باید بگم که روششون کار میکنه ولی به درد ما نمیخوره این روش خیلی کند هست انجام محاسبه تقسیم و باقی مانده
روش سریعتر

behnam6500
28-10-2012, 23:43
متغیر شما حتمن باید 256 عنصری باشه؟

و اینکه گفتی جای جایی پر میشه یعنی به ترتیب ایندکس پر نمیشه درسته؟

agape
29-10-2012, 09:20
میتونید تغییر بدید اندازه رو
در مورد ایندکس هم باید بگم که نه به ترتیب ایندکس پر نمی شه

Aghaeifar
29-10-2012, 11:32
و در مورد نظر آقای M_GH (You can see links before reply) هم باید بگم که روششون کار میکنه ولی به درد ما نمیخوره این روش خیلی کند هست انجام محاسبه تقسیم و باقی مانده
روش سریعتر
روش and بیتی با عدد یک که هی شیفت داده میشه چطور؟

فکر کنم دنبال راه حلی هستید که روی تک تک بیت ها یک بار پردازش مجزا نکنیم. درسته؟

behnam6500
29-10-2012, 14:57
خب چرا اون لحظه ای که تو ارایه میخوای بنویسی، بیتهای مقدار جدید رو نمیشماری؟

اینطوری نیازی نیست که مثلن توی یه حلقه یا هرچیزی بخوای کل بیتهای ارایه رو بشماری!

agape
29-10-2012, 15:32
اون کار رو نمیشه کرد که موقه نوشتن بیت ها رو چک کنیم چرا که سرعت خیلی مهم هست
بله حق با آقای ، آقایی فر هست نمیخوام برای هر بیت شرطی قائل باشم
البته به راهکار رسیدم و الان بیشتر جنبه هوش آزمایی داره:0013:

Shapour_Ardebil
29-10-2012, 20:52
با سلام

امکان دارد هیچ یک از بیتهای مثلا عنصر ارایه شماره 1 اصلا یک نباشد پس چک کردن بیتهای آن وقت تلف کردن است پس اول کل بیتها را چک میکنیم
if(arr[1]>0) اگر بزگتر از صفر بود میتوانیم 16 بیت پایین ویا بالا
int aa=0xffff & arr[1] و
if(aa>0) و حتی 8 بیت بالا و پایین به این ترتیب با کوچک کردن منطقه جستجو زمان را خیلی کوچک میکنیم

agape
30-10-2012, 09:22
خوب میبینم که دوستان دارن هی به جواب نزدیک تر میشن !
آقای Shapour_Ardebil (You can see links before reply) راه کار خوبی هست ولی کافی نیست - من در ابتدا از این روش استفاده کرده بودم ولی باز سرعت کافی نداره !
راه حلی که من پیاده کردم تعداد 90112 بیت رو با فرایند خوندن از SPI و چک کردن بیت های اون الان 90 میلی ثانیه طول میکشه با سرعت 40 مگا هرتزی که 80 میلی ثانیه صرف خوندن از SPI میشه :wink:
منتظر راهکار بهتر شما هستم

Aghaeifar
30-10-2012, 11:26
آقای مزارعی راه حلت رو رو کن دیگه!

احتمالا دنبال همچین چیزی هستی. تست هم کردمش خودم:



int NumberOfSetBits(int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}



تعدادی از الگوریتم های این کار در لینک زیر از دانشگاه استنفورد موجوده

You can see links before reply