Prolog, check if term is power of 2

Question

i have written following code, which should work with my logic, but it does not.

I should check if given term is power of two. For example s(s(s(nul))) should return false, s(s(s(s(nul))) should return true.

substractWhileY(X,0,rezult).
substractWhileY(s(X),Y,rezult):-
   Y > 0, number is 1,  substractWhileY(X,Y - number, rezult).

degreeOftwo(X):-
   substractWhileY(X,2,rezult),
   pagalba(X, 2, rezult).
calculateAnswer(X, currentCounter, currentValue):-
   currentCounter is currentCounter * 2,
   substractWhileY(currentValue, currentCounter , rezult),
   rezult\= null,
   calculateAnswer(X, currentCounter , rezult).

My idea was to check if given therm is degree of any two and if it is not than it is not the degree of two.

With numbers it should work like this. For example i give number 8.

First time it checks if 8 - 2 = 0.
second time if 8 - 4 = 0.
third time if 8 - 8 = 0.

so the 8 id power of two.

Maybe other solution would work better, so thanks for any help.

Answer 1

Assuming that you are looking for numbers 1, 2, 4, 8..., or in other words, 2^0, 2^1, 2^2, 2^3, ..., then a solution that is deterministic could be:

two_power_n(s(X)) :-
    two_power_n_minus_one(X). 

two_power_n_minus_one(0).
two_power_n_minus_one(s(X)) :-
    half(s(s(X)), s(Y)),
    two_power_n_minus_one(Y).

half(0, 0).
half(s(s(X)), s(Y)) :-
    half(X, Y).

I don't think this solution is optimal.

Answer 2

Figuring out if a fixed-point, twos-complement integer is a power of two is easy, utilizing a property of the twos-complement representation used for signed integers in computers:

pow2( X ) :-     % X is a power of 2, if...
  X > 0 ,        % - X is > 0 , and ...
  X is X /\ (-X) % - A bitwise AND of X and its 2s complement yields X
  .              % Easy!

No recursion necessary, just bit-twiddling.

Given that, the solution is easy. Just traverse the nested structure s/1 and compute its depth/length. Then determine whether that is a power of 2 or not.

IsPowerOf2( S ) :- nested_depth(S,0,D) , pow2(D) .

nested_depth( nul  , D , D ).
nested_depth( s(X) , T , D ) :-
  T1 is T+1 ,
  nested_depth(X)
  .

Answer 3

Boris' answer is surely more complete/correct (+1), and I predate his half/2 predicate. But the solution to your question appears simpler in this way:

pow_of_two(s(nul)).
pow_of_two(X) :-
    half(X, H),
    pow_of_two(H).