Господа, перед тем как лезть в алгоритм, объясните мне, пожалуйста, как понимать фразу:

"Suppose n is a k-bit number, that is 2^k-1 <= n < 2^k"

Положим, на примере числа 343. Сколько в нем k-bit? Это единички считать надо? Или просто 8*8?

Пардон, уже дошло. 343 - 9 бит. Только как это подсчитать? Наиболее экономным способом?

n хранится в 32-битном регистре? Если да, то можно сдвигать через carry в сторону MSB до нахождения первой единички.

Да. Пусть n будет unsigned.
Мой алгоритм таков:

unsigned bitcount( unsigned n)
{
	unsigned b;

	for(b = 0; n; n >>= 1)
		b++;

	return b;

}

Как это сделать еще быстрее?

Так?

ecx - n
eax - output value - number of bits

@@:
	shr	ecx, 1
	inc	eax
	test	ecx, ecx
	jne	SHORT @b

volodya

У тя ошипка - нужно eax обнулять перед циклом.


А можно так:

; in:  eax - n,
; out: eax - output value - number of bits 

	test eax,eax
	jz   @F
	bsr eax, eax
@@:	inc eax

BSR r32,r/m32

„Description
Searches the source operand (second operand) for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand (first operand). The source operand can be a register or a memory location; the destination operand is a register. The bit index is an unsigned offset from bit 0 of the source operand. If the contents source operand
are 0, the contents of the destination operand is undefined.“

У тя ошипка - нужно eax обнулять перед циклом.

Ну, ты меня уже совсем за идиота держишь. Я считал, что это очевидно.
А за алгоритм - спасибо. Как всегда, что-то оригинальное придумал :)

Нет конечно, я не держу :)
Просто кто-нить сделает copy-paste и будет удивляться, почему не работает.

:)
Теперь, собственно, к алгоритму. Великолепнейшие объяснения лежат тут:
http://shoup.net/ntb/ - 10.5 - "Perfect Power Testing and Prime Power Factoring".
Громадное спасибо Relf, который дотолкал мне одну слабоочевидную вещь (по крайней мере для меня). Сам алгоритм проиллюстрирован ниже.
Код:

#include <iostream>
#include <math.h>

using namespace std;

/* n must be > 0 */
inline static unsigned bitcount(unsigned n)
{
	unsigned b;

	__asm
	{
		mov eax, n
		bsr eax,eax
		inc eax
		mov b, eax
	}

	return b;
}

void perfect_power(unsigned n)
{
	unsigned k = bitcount(n);
	unsigned e = 2;
	unsigned e_limit = (unsigned)floor(log((double)n)/log(2.0));
	for(;e < e_limit; e++)
	{
		double u = pow(2.0, floor((double)(k-1)/e));
		double v = pow(2.0, ceil((double)k/e));

		do
		{	
			double w = floor((u+v)/2);
			unsigned z = pow(w, (double)e);
			if(z == n)
			{
				cout << "n = d^e: " << n << " = " << w << "^" << e << endl;
				return;
			}
			else if (z < n)
				u = w + 1;
			else
				v = w;
		}while(u < v);
	}
}

void main()
{
	perfect_power(45435424);
}

volodya
Лучше уж так ;-)

@@:
 inc eax
 shr ecx, 1
 jne @B

Нет. Лучше всего как предлагает S.T.A.S. - вообще без цикла :)

Команды тестирования битов медленные так что ещё неизвестно
чей вариант лучше.

Мых-мых, несущественно в данном случае.
Ладно, из уважения к вам, сэр, скажу - мне все равно :)