Loading...
devil619 avatar devil619 62 Точки

[Homework] Java Basics - Syntax - Problem {8*} - Count of Equal Bit Pairs - грешка в условието

Здравейте!

Искам да Ви уведомя за грешка в примерите от Java Syntax Homework (September) на Problem 8. * Count of Equal Bit Pairs.

 

n binary representation of n count
15 1111 3
5343 1010011011111 6
62241 1111001100100001 9

 

На пръв поглед можете да видите, че броя двойки 1-ци на първия пример е 2, а като брой резултат е даден 3, същото е и с другите примери. Ако темата се дублира, моля да ме извините, не можах да намеря подобна тема. :)

0
Java Advanced 14/09/2014 10:49:28
devil619:
Темата е изчерпана и няма какво още да се добави към нея.
a.polyanska avatar a.polyanska 107 Точки

Аз също имам въпрос по задачата (питах вече в друга тема, но не получих отговор, та да пробвам пак). Логиката на решението ми е такава- очевидно, като гледаме примерите, трябва  да преброим двойките като започнем от първият ЗНАЧИМ бит, т.е единичка (нулите в началото ги пропускаме). Ето кода ми: http://pastebin.com/pKEnxj1v

Първият цикъл се върти докато битът на съответната позиция не стане 1 и тогава броячът (j) ни става крайна стойност, до която се върти вторият цикъл, с който броим двойките еднакви битове.

Проблемът е, че когато започваме да вадим битовете от 31ва позиция надолу, при j=31 (т.е. при 2 на степен) не ми дава резултат 1 на 31ва позиция и останалите нули, а единички на всяка позиция. Когато j < 31 няма такъв проблем (когато се пусне през дебъгера става ясно какво имам предвид). Някой има ли идея защо се получава така? Да няма нещо, което ми убягва, свързано със знака на интеджъра?

0
Filkolev avatar Filkolev 4482 Точки

Битът на позиция 31 при типа int показва знака на числото. Ако ти подават положителни числа той винаги ще е 0. Това, което правиш, ще препълни int-a, неговата максимална стойност е 2^31 - 1.

По-безопасно е да вървиш отдясно наляво в while цикъл, да местиш числото надясно след като провериш дадена позиция и да спреш, когато числото стане 0. Така няма да има значение точно къде е първата единица. Има също начини да проверяваш по две числа едновременно, облекчава сметките.

Последния цикъл би трябвало да е не до 31, а до pos - 1, нали това е цялата идея на първия цикъл, да видиш къде да спреш. А може би си сложила 31, защото не ти работи изчисляването на pos? Но както казах, по-добре го смени с while (num > 0) примерно.

1
13/09/2014 01:15:57
a.polyanska avatar a.polyanska 107 Точки

Последният цикъл не е (или поне според мен не е :) ) до 31, а до j. Задала съм му първоначална стойност 31, за да го инициализирам, но би трябвало да се запазни последната му стойност, при която е завъртян цикъла за проверка.

Честно казано, не разбрах точно идеята с местенето надясно докато числото стане 0. Как ще разберем по този начин коя е значимата позиция?

И още- ако се върнем на моя начин, значи ли, че ако задам цикъла не от 31, а от 30 ще се реши проблемът?

0
Filkolev avatar Filkolev 4482 Точки

Аха, да, сега видях, че j е декларирана по-нагоре, стандартното е да се ползва само за цикъла и не го забелязах.

С while няма значение къде е последната единица - местиш числото надясно, лека-полека тази единица се придвижва надясно и самото число намалява (операцията >> 1 е аналогична на деление на 2). В един момент единицата ще дойде най-вдясно, след което ще изчезне и числото вече ще е нула. Тогава трябва да се спре цикъла, защото нататък следват само нули, които ще се преброят в брояча. Даже може да се спре цикъла една стъпка по-рано (на предпоследна стъпка примерно имаме число в двоична бройна система 001х, реално няма нужда да местим пак надясно, защото е ясно, че повече двойки битове няма - ще получим 0001 и на следващата стъпка вече 0). Т.е. може while (number > 1) да е условието, пак би трябвало да работи.

По твоят начин, би трябвало да проработи ако провериш първо 30-та позиция и вървиш наляво. Както казах, ако ти се подават само положителни числа тип int, това е последната позиция, на която може да имаме 1, ако на позиция 31 има 1, значи числото е отрицателно. Мисли за бит 31 като за знака на числото - 0 => "+", 1 => "-". А както повдигаш 2 на степен 31 и после обръщаш в int, това е по-голяма стойност от максималната му стойност. Смени 31 с 30 и виж дали става, вероятно ще се получи.

1
a.polyanska avatar a.polyanska 107 Точки

Супер, браво, много благодаря! Просветна ми :) Едно иф-че сложих (ако n стане нула, прекъсва цикъла) и се получи идеално. Пак много благодаря!

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.